DSA Factory
Free Recursion lessonsRecursion · Stage 3 · Include or skip · Step 1

Take it or leave it

Count the ways to pick some of the values so they add up to a target, by deciding for each value to take it or skip it. About 14 minutes.

Two doors for every value

Imagine standing in front of the values one at a time. For each, you either put it in your bag or leave it out. A way of picking is the full list of those choices. How many ways give a bag whose total is exactly the target?

Handle the first value, then hand the remaining values to the same function. If you take the value, the remaining target drops by it. If you leave it, the target stays. The answer is the sum of the two branches.

Take it: recurse with the target reduced by the value.
Leave it: recurse with the same target.
In code
def subsets(i):
    if i == len(nums):
        return 1
    take = subsets(i + 1)
    skip = subsets(i + 1)
    return take + skip
Values 1, 2, 3 and a target of 3. Decide one value at a time.
1
0
2
1
3
2
leftright

Start with 3 left to reach, and decide the value 1. Take it (2 left) or leave it (3 left).

Move 1 of 4

The base case at the end

When you've decided on every value, you're at the end of the list. That choice of values is a valid way only if exactly zero is left to reach. So return 1 for zero left and 0 for anything else, whether positive or negative.

Because the values are never negative, you can also stop early when the target goes negative: no more taking can fix it. That is an optional shortcut. The empty bag counts as a way when the target is 0.

End, zero left: one way.
End, anything else: no ways.
Quick check

With one value left (a 4) and 4 still to reach, how many ways does the call count?

  1. A1: take the 4, leaving nothing; skipping it leaves 4 unreached
  2. B2, one for each choice
  3. C0
Show the answer

1: take the 4, leaving nothing; skipping it leaves 4 unreached. Taking it ends at zero left (one way), and skipping it ends with 4 left (no ways).

Your problem

Ways to pick

nums is a list of non-negative whole numbers and target is a non-negative whole number. Count the ways to choose some of the values (possibly none) so that they add up to target. Two ways are different if they choose different positions, even if the values are equal. Use a recursive function that decides each value in turn.

Example
nums = [2, 3, 5], target = 5 → 2

0 ≤ length ≤ 20 · 0 ≤ value ≤ 20 · 0 ≤ target ≤ 200

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.
Sign up free to solve