Count Subsets with Sum K
easyDynamic Programming II+10 XPTime limit 2s
A teacher has n chocolates with weights a[1] … a[n] grams. In how many ways can she pick a subset of chocolates whose weights add up to exactly k grams? Chocolates are told apart by position, so two chocolates of equal weight make different subsets. The empty subset counts when k = 0. Print the count modulo 1 000 000 007.
Input:
- line 1:
n k - line 2:
nweights
Output: the number of subsets modulo 10⁹ + 7.
Constraints: 1 ≤ n ≤ 1000, 0 ≤ k ≤ 1000, 0 ≤ a[i] ≤ 1000. Note that a weight may be 0.
Think about it: ways[s] = number of subsets of the items seen so far with sum s. Each new item either stays out or joins: ways[s] += ways[s − a[i]], looping s downwards. A weight of 0 doubles every count — make sure your loop handles it.
Sample input 1
6 10 2 3 5 6 8 10
Sample output 1
3
Sample input 2
3 1 0 0 1
Sample output 2
4
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).