【Go】bit全探索のサンプルコード

概要

• 2進法を用いて、配列内の要素を「選ぶ」「選ばない」の全ての組み合わせを表現
• 組み合わせの数 = 2^N
  • N = 3 = 2^3 = 8種類
• 計算量は2^N
  • N=20までなら使える

ものすごく簡単な例

3種類の数値[1, 2, 3]の内、合計が4になる組み合わせの数

◯と1は選ぶ、✗と0は選ばないとしている

8組目のみ合計が4になるので組み合わせの数は1つ

	◯✗	2進法	合計
	1, 2, 3	1, 2, 3
1組目	✗,✗,✗	000	0=0
2組目	◯,✗,✗	100	1=1
3組目	◯,◯,✗	110	1+2=3
4組目	◯,◯,◯	111	1+2+3=6
5組目	✗,◯,◯	011	2+3=5
6組目	✗,◯,◯	011	2+3=5
7組目	✗,◯,✗	001	2=2
8組目	◯,✗,◯	101	1+3=4

サンプルコード

// CountSubsetSum は集合の中から合計が target になる組み合わせの数を返す関数
// nums: 数値の集合
// target: 目標の合計値
// 戻り値: 条件を満たす組み合わせの数
func CountSubsetSum(nums []int, target int) int {
	n := len(nums)
	count := 0
	
	// 2^n 通りのパターンを全探索
	for bit := 0; bit < (1 << n); bit++ {
		sum := 0
		
		// 各ビットをチェックして、対応する要素を合計に加える
		for i := 0; i < n; i++ {
			if (bit >> i) & 1 == 1 {
				sum += nums[i]
			}
		}
		
		// 合計が目標値と一致する場合、カウントを増やす
		if sum == target {
			count++
		}
	}
	
	return count
}

nums := []int{1, 2, 3}
target := 4
count := CountSubsetSum(nums, target)
fmt.Println(count1, "通り")

// 出力
// 1通り