概要

\(N\) 個の商品からいくつか選び、その合計金額をちょうど \(K\) 円にする方法の数を求めよ。各商品は最大で1つしか選べない。

考察

この問題は典型的な「部分和問題（Subset Sum Problem）」の亜種であり、「各商品を最大1回だけ使って、合計をちょうど \(K\) 円にする方法は何通りあるか？」という問題です。

素朴な方法として、全組み合わせを試すことを考えると、商品の選び方は \(2^N\) 通りあり、\(N\) が最大100なので、これは現実的ではありません（計算量 \(O(2^N)\)）。また、同じ商品を複数回使わないようにしなければならないため、単純な再帰やビット全探索でも実装は難しいです。

そこで、動的計画法（DP）を利用します。特に「各商品を高々1回使う」という制約があるため、「ナップサック問題」の一種と考えることができます。

DPテーブルとして以下のように定義します： - dp[i] := 合計金額がちょうど \(i\) 円になるような選び方の数

初期値として dp[0] = 1 （何も選ばないという1通り）を設定し、各商品に対してDPテーブルを更新していきます。

ここで重要なのは、商品を「後ろから」見ていくことです。これにより、1つの商品が複数回使われるのを防ぎます。もし前から更新してしまうと、同じ商品を何度も使うことになり得ます。

例えば、商品価格が [2, 3] で \(K=5\) の場合、最初の商品 2 を処理した時点で dp[2] = 1 になります。次に商品 3 を処理するときに dp[5] += dp[2] と更新できます。

アルゴリズム

動的計画法（DP）を用います。

DPの定義

• dp[i] := 合計が \(i\) 円となる選び方の数
• 初期化：dp[0] = 1、それ以外は 0

更新則

各商品の価格を \(h\) としたとき、\(K\) 円から \(h\) 円まで逆順に更新します：

\[ \text{for } j = K \text{ downto } h: \\ \quad dp[j] = (dp[j] + dp[j - h]) \bmod (10^9 + 7) \]

このように「大きい金額から小さい方に向かって」更新することで、各商品を最大1回しか使わないようにできます。

最終的な答え

dp[K] が求める組み合わせの数です。

計算量

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

実装のポイント

• 商品を「後ろから」ループすることで、各商品が1度しか使われないようにする
• DPテーブルは MOD = 10^9 + 7 で毎回剰余を取ることでオーバーフローを防ぐ
• 入力を高速に読み込むことで、Pythonでも時間内に動作させる工夫が必要（sys.stdin.readなど）

## ソースコード

```python
MOD = 10**9 + 7

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    H = list(map(int, data[2:]))
    
    # dp[i] := 合計が i 円になる組み合わせの数
    dp = [0] * (K + 1)
    dp[0] = 1
    
    for h in H:
        # 後ろから更新することで、各商品を一度だけ使う制約を満たす
        for j in range(K, h - 1, -1):
            dp[j] = (dp[j] + dp[j - h]) % MOD
    
    print(dp[K])

if __name__ == "__main__":
    main()

---

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