A numismatist owns n coins, each with a whole-number face value (values may repeat). Count the number of subsets of coins whose face values add up to exactly T. Two subsets are different if they consist of a different set of coin positions, even when the multisets of values look the same. The empty subset sums to 0.
Line 1: two integers n and T.
Line 2: n space-separated integers, the coin face values.
A single integer: the number of coin subsets summing to exactly T.
Example 1
Input
4 6 1 2 3 4
Expected
2
Explanation
The subsets {2,4} and {1,2,3} each sum to 6, so the count is 2.
Example 2
Input
3 0 5 6 7
Expected
1
Explanation
Only the empty subset sums to 0 (all values are positive), so the count is 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →