Overview

This problem asks us to select some items from \(N\) items such that their total cost is exactly \(K\) yen, and find the number of such combinations. This is a type of well-known problem called the “subset sum problem,” which can be solved efficiently using dynamic programming (DP).

Analysis

1. Limitations of Brute Force

The simplest approach is to try all possibilities of “buy” or “don’t buy” for each item. However, when there are \(N\) items, the total number of combinations is \(2^N\). In this problem, since \(N \le 100\), we get \(2^{100} \approx 1.26 \times 10^{30}\), making it impossible to complete the computation within the time limit.

2. Converting to Dynamic Programming (DP)

If we focus on the “current total cost,” we notice that combinations leading to the same total amount appear repeatedly. Therefore, we define the following state to make the computation more efficient.

dp[i][j]: the number of ways to make a total cost of \(j\) yen using items up to the \(i\)-th one

When considering the \(i\)-th item (with price \(H_i\)), the state transitions as follows: - When not buying the \(i\)-th item: The total cost remains unchanged, so it stays at dp[i-1][j] ways. - When buying the \(i\)-th item: The total cost increases by \(H_i\) to reach \(j\) yen, so the previous state has dp[i-1][j - H_i] ways (only when \(j \ge H_i\)).

The sum of these gives dp[i][j].

Algorithm

Dynamic Programming (Space Optimization)

Implementing dp[i][j] directly requires \(O(N \times K)\) memory, but we can save space by reusing a one-dimensional array dp[j].

1. Prepare an array dp of size \(K+1\) and initialize it with 0.
2. Since the state of selecting nothing (total of 0 yen) has exactly 1 way, set dp[0] = 1.
3. For each item \(H_i\), repeat the following process:
   • Loop over the amount \(j\) in reverse order from \(K\) yen down to \(H_i\) yen.
   • Update as dp[j] = (dp[j] + dp[j - H_i]) % mod.

Why update in reverse order? If we update in forward order (from \(H_i\) to \(K\)), the results of selecting the same item multiple times (duplicate usage) would be added. By updating from the back, we can reference values from the state “before the currently considered item \(H_i\) has been selected,” thus satisfying the condition that each item is used at most once.

Complexity

• Time complexity: \(O(N \times K)\)
  • This involves a double loop over the number of items \(N\) and the target amount \(K\). The computation is on the order of \(100 \times 10000 = 10^6\), which is well within the time limit.
• Space complexity: \(O(K)\)
  • Since we only maintain a one-dimensional DP table, this is very efficient.

Implementation Notes

• When to take the modulus: Since the number of combinations can become extremely large, we compute the remainder when divided by \(10^9 + 7\) every time we perform an addition.

• Initialization: Don’t forget to set dp[0] = 1. This represents the single way of “selecting nothing.”

• Loop range: Python’s range(k, price - 1, -1) generates values in reverse order from \(K\) down to price.

  Source Code

import sys

def solve():
    # 入力の読み込み
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    k = int(input_data[1])
    h = list(map(int, input_data[2:]))
    
    mod = 10**9 + 7
    
    # dp[j] は合計金額が j 円になる組み合わせの数
    dp = [0] * (k + 1)
    dp[0] = 1
    
    for price in h:
        # 重複して選ばないように、後ろから更新する
        for j in range(k, price - 1, -1):
            dp[j] = (dp[j] + dp[j - price]) % mod
            
    print(dp[k])

if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3-flash-preview.