概要
- 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通り