ビット全探索で部分集合を列挙

選ぶ・選ばないの N 個の判断を、N 桁の2進数に対応させます。全体で 2^N 通りです。

言語：Python / 計算量：O(N 2^N)

前提：全探索は「漏れなく、重複なく」

考え方

1. mask の i 桁目が1なら i 番目を選びます。
2. mask >> i & 1 でその桁を調べます。
3. 空集合も1つの候補です。

具体例

3要素なら mask=5 は2進数で101。0番目と2番目を選びます。

実装

a = [2, 3, 5]
for mask in range(1 << len(a)):
    total = 0
    for i, x in enumerate(a):
        if mask >> i & 1:
            total += x
    print(mask, total)

注意する条件

N=40 なら約1兆通り。半分全列挙やDPへ切り替える規模です。

確認問題

4要素の部分集合は空集合込みで何通り？

実装課題

N K と配列 A。和がKとなる部分集合の個数を求める。0 ≤ N ≤ 18、0 ≤ A_i,K ≤ 10^6。添字で区別。空集合も含む。

入力:
3 5
2 3 5
出力:
2

n, k = map(int,input().split())
a = list(map(int,input().split()))
ans = 0
for mask in range(1 << n):
    s = 0
    for i in range(n):
        if mask >> i & 1:
            s += a[i]
    ans += s == k
print(ans)

読了の記録・下書き・メモへ