Subsets with Target Sum
Hard 70 XPRecursionDynamic Programming
Commonly asked at Amazon, Microsoft
Read a list of positive integers and a target. Print how many subsets (any selection of positions, including choosing none) add up exactly to the target.
- Input
- Line 1: positive integers (up to 30 of them). Line 2: target (0 ≤ target ≤ 1000).
- Output
- Number of subsets.
Sample 1
Input
2 3 5 6 8 10 10
Output
3
Explanation: {2,8}, {10}, {2,3,5}
Read input with input() (no prompt message) and print only the answer. Run tries the Input box; Submit checks all test cases.
Output Loading Python (first time takes a few seconds)
Press Run to see the result here.The solution unlocks after 3 submissions.