Overview

This is a problem where you choose each item as either “buy/don’t buy” and count the number of ways (subsets) such that the total price is exactly \(K\).

Analysis

• Since “each item can be bought at most once,” the chosen set is a subset of \(N\) elements. We want to find “the number of subsets whose total price equals \(K\).”
• Naively trying all subsets gives \(2^N\) possibilities, which is not feasible for \(N \le 100\) (TLE).
• Therefore, we use dynamic programming (DP) that incrementally updates “the number of ways to achieve each total price.”
• The key point is “the same item must not be used more than once.” To ensure this, we update the total price from larger to smaller (in reverse order).
  If we update from smaller to larger, the same item gets added multiple times within a single processing step (turning it into an unbounded DP), resulting in a wrong answer (WA).

(Example) When \(H=[3]\), \(K=6\): this should be impossible (cannot buy 3 twice), but with forward-order updates, the value of \(dp[3]\) updated just before gets used to also increment \(dp[6]\).

Algorithm

We perform a 0/1 knapsack-style “counting DP.”

• Define \(dp[s]\) as “the number of ways to make the total price exactly \(s\) using only the items considered so far.”
• The initial state is: there is exactly 1 way to make a total of \(0\) by selecting nothing, so \(dp[0]=1\), and all others are \(0\).
• For each item’s price \(h\), iterate the total price \(s\) from \(K\) down to \(h\) in reverse order, and update: [ dp[s] \leftarrow dp[s] + dp[s-h] ] This means: by adding “this item (price \(h\))” to “a way to make total \(s-h\),” we can make total \(s\).
• The answer is \(dp[K]\) (taken modulo \(10^9+7\)).

Complexity

• Time complexity: \(O(NK)\)
• Space complexity: \(O(K)\)

Implementation Notes

• The loop over total prices must be in reverse order (for s in range(K, h-1, -1)). This guarantees that each item is used at most once.

• At each update, take MOD = 10**9+7 to prevent overflow and excessively large values.

• Since \(H_i \le K\), it is sufficient to only update for \(s \ge h\).

  Source Code

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

This editorial was generated by gpt-5.2-high.