Count how many groups of numbers add up to a target.
What to build
A recursive function that tries every combination.
Requirements
- Read the numbers and the target.
- Print how many subsets of the numbers add up exactly to the target.
- The empty group counts as a subset, with a sum of 0. Numbers at different positions count as different, even if they are equal.
Input
The first line has n and target. The second line has n whole numbers.
Output
One number.
Constraints
n is from 1 to 15. All values are from 0 to 1000.
Example
Input:
3 5
2 3 5
Output:
2
Why it works
Each number doubles the choices, and recursion explores both branches. The base case runs when every number has been decided, so every subset is checked exactly once.
Examples
Example 1 · Input
3 5 2 3 5
Expected output
2
Example 2 · Input
4 0 1 2 3 4
Expected output
1
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
For each number, there are two choices: use it, or leave it out.
Hint 2
Write ways(i, target), where i is the position of the next number to decide on.
Hint 3
When i reaches the end, the choice is finished: count 1 if target is 0, otherwise 0.
Solution
Show one correct solution (try it yourself first)
n, target = [int(x) for x in input().split()]
nums = [int(x) for x in input().split()]
def ways(i, remaining):
if i == n:
return 1 if remaining == 0 else 0
return ways(i + 1, remaining) + ways(i + 1, remaining - nums[i])
print(ways(0, target))