概要

各商品を「買う/買わない」のどちらかで選び、合計金額がちょうど \(K\) になる選び方（部分集合）の個数を数える問題です。

考察

• 「各商品は最大1個まで」なので、選ぶ集合は \(N\) 個の要素からなる部分集合 です。求めたいのは「価格合計が \(K\) になる部分集合の数」です。
• 素朴に全部の部分集合を試すと \(2^N\) 通りあり、\(N \le 100\) では現実的に間に合いません（TLE）。
• そこで、「合計金額ごとの作り方の数」を段階的に更新していく 動的計画法（DP） を使います。
• 重要な点は「同じ商品を複数回使ってはいけない」ことです。これを守るために、合計金額の更新を 大きい方から小さい方へ（逆順） に行います。
  もし小さい方から更新すると、同じ商品を1回の処理中に何度も足してしまい（無制限個使えるDPになり）誤答（WA）になります。

（例）\(H=[3]\), \(K=6\) のとき、本来は作れない（3を2回買えない）が、順方向更新だと \(dp[3]\) を更新した直後の値を使って \(dp[6]\) まで増えてしまいます。

アルゴリズム

0/1 ナップサック型の「個数を数えるDP」を行います。

• \(dp[s]\) を「ここまで見た商品だけを使って、合計金額をちょうど \(s\) にする方法の数」と定義します。
• 初期状態は、何も選ばず合計 \(0\) を作る方法が1通りなので \(dp[0]=1\)、それ以外は \(0\)。
• 各商品の価格 \(h\) について、合計金額 \(s\) を \(K\) から \(h\) まで逆順に動かし、 [ dp[s] \leftarrow dp[s] + dp[s-h] ] とします。
  これは「合計 \(s-h\) を作る方法」に「この商品（価格 \(h\)）を追加」することで合計 \(s\) を作れる、という意味です。
• 答えは \(dp[K]\)（\(10^9+7\) で割った余り）です。

計算量

• 時間計算量: \(O(NK)\)
• 空間計算量: \(O(K)\)

実装のポイント

• 合計金額のループは必ず逆順（for s in range(K, h-1, -1)）。これで各商品を高々1回しか使わないことが保証されます。

• 各更新で MOD = 10**9+7 を取ってオーバーフローと値の増大を防ぎます。

• \(H_i \le K\) なので、更新範囲は \(s \ge h\) のみで十分です。

  ソースコード

import sys

MOD = 10**9 + 7

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    H = list(map(int, input().split()))
    
    dp = [0] * (K + 1)
    dp[0] = 1
    for h in H:
        for s in range(K, h - 1, -1):
            dp[s] = (dp[s] + dp[s - h]) % MOD
    
    print(dp[K] % MOD)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。