You are given n positive integers and a target t. Count the number of subsets (chosen by index, so equal values at different positions are different elements) whose elements sum to exactly t. The empty subset has sum 0.
Line 1: an integer n.
Line 2: n space-separated positive integers.
Line 3: the target t.
A single integer: the number of subsets summing to t.
Example 1
Input
5 1 2 3 4 5 5
Expected
3
Explanation
Subsets summing to 5 are {5}, {1,4} and {2,3} — three of them.
Example 2
Input
3 2 2 2 2
Expected
3
Explanation
Each of the three 2s forms its own subset of sum 2, and they are distinguished by index, so the answer is 3.
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 →