問題
$N$ 個の整数 $a_1,\dots,a_N$ と整数 $K$ が与えられる。総和がちょうど $K$ になる部分集合（空集合を含む）の個数を求めよ。
制約
| パラメータ | 範囲 | 備考 |
|---|---|---|
| $N$ | $1 \le N \le 40$ | $2^{40}$ は直接列挙不可 |
| $a_i$ | $0 \le a_i \le 10^9$ | 非負整数 |
| $K$ | $0 \le K \le 4\times10^{10}$ | 目標和 |
入出力例
入力例1
4 5
1 2 3 4出力例1
2$\{1,4\}$ と $\{2,3\}$ の2通りが和 5 になる。
概念図: 前半・後半に分けて二分探索でマージ
ヒント
ヒント1（方向性）
$N \le 40$ では $2^{40}$ 通りの直接列挙は不可能。配列を半分に分ければ、それぞれ $2^{20}$ 通り程度になり列挙可能になる。
ヒント2（アプローチ）
前半・後半それぞれの全部分集合和を列挙し（$O(2^{N/2})$）、後半をソートしておく。前半の各和 $s$ について「後半の和が $K-s$ に一致する個数」を二分探索で数え、足し合わせる。
ヒント3（ほぼ答え）
from bisect import bisect_left, bisect_right
def subset_sums(arr):
sums = [0]
for x in arr:
sums = sums + [s + x for s in sums]
return sums
# ans += bisect_right(right, K-s) - bisect_left(right, K-s) for s in left模範解答
import sys
from bisect import bisect_left, bisect_right
def subset_sums(arr):
sums = [0]
for x in arr:
sums = sums + [s + x for s in sums]
return sums
def solve():
data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
a = list(map(int, data[2:2 + n]))
half = n // 2
left = subset_sums(a[:half])
right = subset_sums(a[half:])
right.sort()
ans = 0
for s in left:
need = k - s
if need < 0:
continue
ans += bisect_right(right, need) - bisect_left(right, need)
print(ans)
solve()計算量: $O(2^{N/2}\cdot N) + O(2^{N/2}\log 2^{N/2})$。$N=40$ でも $2^{20}\approx10^6$ で実行可能。
Step-by-Step 解説
Step 1: 半分に分割
half = n // 2 で配列を前半・後半に分ける。両側とも高々 $2^{20}$ 通り。
Step 2: 部分集合和の列挙
subset_sums はリストを2倍に増やしながら「含む/含まない」を反復列挙する古典的テクニック。初期値 $[0]$ が空集合の和。
Step 3: ソート＋二分探索でマージ
後半をソートし、前半の各和 $s$ に対して bisect_left/bisect_right の差で「和が $K-s$ の個数」を数える。重複した和も正しくカウントできる。
Step 4: 計算量の確認
$2^{N/2}$ 通りの列挙・ソート・二分探索、いずれも $N=40$ で現実的な時間に収まる。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
right.count(need) で数える | 呼び出しごとに $O(2^{N/2})$ で全体 $O(2^N)$ に劣化 | ソート済み配列に bisect の差で $O(\log)$ |
| 空集合を数え忘れる | subset_sums の初期値を [] にしてしまう | 初期値は [0] |
| 分割が偏る | half = n など片方に全部詰める | ほぼ均等な n // 2 で分割 |
次のステップ
- 発展問題: 「和が $K$ に最も近い部分集合」（両側ソート + two-pointer で $O(2^{N/2})$）
- 発展問題: 複数クエリ $K_1,\dots,K_Q$ への対応
自己評価
理解度: / /
自分の回答:
気づき・メモ: