Branching calls: take it or leave it

In some problems every step holds a choice: take this element or leave it, put an opening bracket here or a closing one. Recursion tries both: it calls itself once for each. The calls are no longer a chain but a tree.

1def count(values, i, left):
2    if left == 0:
3        return 1
4    if i == len(values) or left < 0:
5        return 0
6    take = count(values, i + 1, left - values[i])
7    skip = count(values, i + 1, left)
8    return take + skip

Take values[i] and the target shrinks by that much; leave it and the target stays; either way you move on to the next element. This version counts the ways; for "is there one?" you return take or skip.

The price is high: every element doubles the number of calls. 20 elements are a million calls, 30 a billion. So two questions matter in branching recursion: can I cut a branch early (stop once the target goes negative), and am I solving the same sub-problem again and again? The answer to the second is the Dynamic Programming topic.

Tasks