Advanced · Recursion · 163 of 264
Subsets with a sum
Count the subsets (choices of positions) of the list whose numbers add up to the target. The empty subset counts when the target is 0.
Input: up to 18 whole numbers on one line, then the target. Output: the number of subsets.
Examples
Input
1 2 3 4 5 5
Output
3
Input
1 1 1 2
Output
3
Input
2 4 6 1
Output
0
2 more tests check other inputs when you press Check.
Stuck? The idea behind recursion
A recursive function calls itself on a smaller version of the problem, until it reaches a case small enough to answer directly (the base case).
Trust the smaller call to be right, and only work out how to build this answer from it.
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(5))Watch for: Without a base case, or if the problem doesn't get smaller, it never stops: Python gives up with a RecursionError.