半分全列挙で指数を半分に

2^40 は大きすぎても、2^20 を2回なら候補数が大きく下がります。左右の部分集合和を組み合わせます。

言語：Python / 計算量：O(2^(N/2)) 平均（辞書使用）、同程度のメモリ

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

考え方

1. 配列を左右に分けます。
2. それぞれの部分集合和をすべて作ります。
3. 片側を辞書やソート済み配列にして、補数を探します。

具体例

[2,3] と [5] に分けると左の和は0,2,3,5、右は0,5。和5は (0,5),(5,0) の2通りです。

実装

from collections import Counter
def sums(a):
    s=[0]
    for x in a:s += [v+x for v in s]
    return s
a=[2,3,5];k=5
l=sums(a[:1]);r=Counter(sums(a[1:]))
print(sum(r[k-x] for x in l))

注意する条件

Pythonの整数リストと辞書はメモリを多く使います。N=40でも常に安全とは限りません。

確認問題

20要素の部分集合数は？

実装課題

N K と配列 A。和Kの部分集合数（添字で区別）。N≤32、|A_i|,|K|≤10^9。

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

from collections import Counter
n,k=map(int,input().split());a=list(map(int,input().split()))
def sums(a):
    s=[0]
    for x in a:s += [v+x for v in s]
    return s
l=sums(a[:n//2]);r=Counter(sums(a[n//2:]))
print(sum(r[k-x] for x in l))

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