Loading...
Loading...
Loading...
A list has N positive numbers. Count the subsets of positions whose numbers add up to exactly T. Two subsets are different if they use different positions, even if the numbers are equal.
Example
Input
5 6 1 2 3 3 4
Output
4
1+2+3 twice, 2+4 and 3+3.
Try the problem first. Open one hint at a time.
Let ways[s] be the number of subsets with total s. Start with ways[0] = 1.
For each number x, add ways[s - x] to ways[s], looping s downwards.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor