概要

\(N\) 種類のお菓子の中からいくつか選び、その合計金額をちょうど \(S\) 円にする方法の数を求めよ。

考察

この問題は「部分集合の和が \(S\) になる選び方は何通りあるか？」という典型的な部分和問題の応用です。しかし、制約が厳しいため単純な全探索では間に合いません。

例えば、各お菓子について「買う」「買わない」の2択があるため、全部で \(2^N\) 通りの選び方があります。\(N\) が最大 \(40\) なので、\(2^{40} \approx 10^{12}\) となり、現実的な時間内に計算できません。

そこで登場するのが 半分全列挙 というテクニックです。配列を前半と後半の2つに分割し、それぞれの部分集合の和を全列挙します。これにより、計算量を \(O(2^N)\) から \(O(2^{N/2})\) へと削減できます。

具体的には： - 前半の部分集合の和をすべて求め、ハッシュテーブル（辞書）にその出現回数を記録します。 - 後半についても同様に行います。 - 最後に、「前半の和 + 後半の和 = \(S\)」となる組み合わせの数をカウントします。

たとえば、前半の和が \(x\) であるものが \(a\) 通りあり、後半の和が \(S - x\) であるものが \(b\) 通りあるなら、その積 \(a \times b\) だけ条件を満たす選び方があります。

このようにして、計算量を大幅に削減しながら答えを求めることができます。

アルゴリズム

1. 配列 \(A\) を前半 left と後半 right に分割する。
2. left のすべての部分集合について、その要素の和を計算し、left_sums という辞書に記録（キー：和、値：その和になる部分集合の個数）。
3. 同様に right についても right_sums を作成。
4. left_sums の各キー \(ls\) に対して、\(S - ls\) が right_sums に存在すれば、その積を答えに加算。
5. 答えを出力。

計算量

• 時間計算量: \(O(N \cdot 2^{N/2})\)
• 空間計算量: \(O(2^{N/2})\)

実装のポイント

• defaultdict(int) を使うことで、キーが存在しなくてもエラーにならず初期値0として扱える。
• ビット演算（bitmask）を使って部分集合を列挙している。
• 入力を高速に読み込むために sys.stdin.read を使用している。

ソースコード

from collections import defaultdict

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    S = int(data[1])
    A = list(map(int, data[2:]))

    # 半分全列挙
    mid = N // 2
    left = A[:mid]
    right = A[mid:]

    # 左半分のすべての部分集合の和を計算
    left_sums = defaultdict(int)
    for mask in range(1 << len(left)):
        s = 0
        for i in range(len(left)):
            if mask & (1 << i):
                s += left[i]
        left_sums[s] += 1

    # 右半分のすべての部分集合の和を計算
    right_sums = defaultdict(int)
    for mask in range(1 << len(right)):
        s = 0
        for i in range(len(right)):
            if mask & (1 << i):
                s += right[i]
        right_sums[s] += 1

    # 結果を計算
    count = 0
    for ls, lc in left_sums.items():
        need = S - ls
        if need in right_sums:
            count += lc * right_sums[need]
    
    print(count)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。