Skills101
← All coding problems

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: n weights

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

Loading editor…

Log in to run and submit your code — it's free.