A treasure chest holds n items, each with a positive integer weight. Items are distinct objects even if two of them happen to weigh the same. Count how many subsets of the items have a total weight exactly equal to a target T.
The empty subset has total weight 0. Two subsets are different if they use a different set of item positions.
Line 1: two integers n and T.
Line 2: n space-separated positive integers, the item weights.
A single integer: the number of subsets whose weights sum to exactly T.
Example 1
Input
3 5 2 3 5
Expected
2
Explanation
Subsets summing to 5 are {2,3} and {5}, so the answer is 2.
Example 2
Input
3 0 1 2 3
Expected
1
Explanation
All weights are positive, so only the empty subset sums to 0: the answer 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 →