Overview

Given \(N\) items, select some of them such that the total price is exactly \(K\) yen. Find the number of ways to do this. Each item can be selected at most once.

Analysis

This problem is a variant of the classic “Subset Sum Problem”: “How many ways are there to make the total exactly \(K\) yen, using each item at most once?”

A naive approach would be to try all combinations. There are \(2^N\) possible selections, and since \(N\) can be up to 100, this is not practical (time complexity \(O(2^N)\)). Moreover, since each item cannot be used more than once, even simple recursion or bit-based exhaustive search would be difficult to implement efficiently.

Therefore, we use dynamic programming (DP). In particular, since there is a constraint that “each item can be used at most once,” this can be thought of as a type of “knapsack problem.”

We define the DP table as follows: - dp[i] := the number of ways to select items such that the total price is exactly \(i\) yen

We set the initial value dp[0] = 1 (one way: selecting nothing), and update the DP table for each item.

The key point here is to iterate through the amounts in reverse order (from back to front). This prevents a single item from being used multiple times. If we update from front to back, the same item could end up being used more than once.

For example, if the item prices are [2, 3] and \(K=5\), after processing the first item with price 2, we have dp[2] = 1. Then, when processing item with price 3, we can update dp[5] += dp[2].

Algorithm

We use dynamic programming (DP).

DP Definition

• dp[i] := the number of ways to select items such that the total is \(i\) yen
• Initialization: dp[0] = 1, all others are 0

Update Rule

For each item with price \(h\), update in reverse order from \(K\) yen down to \(h\) yen:

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

By updating “from larger amounts toward smaller amounts” like this, we ensure that each item is used at most once.

Final Answer

dp[K] is the desired number of combinations.

Time Complexity

• Time complexity: \(O(N \cdot K)\)
• Space complexity: \(O(K)\)

Implementation Notes

• By looping through amounts in reverse order, we ensure each item is used only once

• Take the modulus with MOD = 10^9 + 7 at every DP table update to prevent overflow

• To run within the time limit even in Python, it is necessary to read input efficiently (e.g., using sys.stdin.read)

  Source Code

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()

---

This editorial was generated by qwen3-coder-480b.