Prune Early: Combinations That Hit a Total
A post office sells stamps worth 2, 3 and 5 cents, as many of each as you like. A parcel needs exactly 8 cents of postage. Which stamp combinations work? Listing every possible pile of stamps and then checking the totals would explore a huge tree full of hopeless branches. Good backtracking cuts those branches off the moment they are doomed.
The rule
Stop a branch the moment it can no longer succeed.
Cutting off a doomed branch is called pruning. Here, a branch is doomed as soon as the next stamp is bigger than the postage still needed. Sort the values first, and one such stamp proves every later stamp is too big as well, so the loop can break, not just skip:
def ways_to_total(values, target):
values = sorted(values)
result, path = [], []
def explore(start, remaining):
if remaining == 0:
result.append(path[:])
return
for i in range(start, len(values)):
value = values[i]
if value > remaining:
break # sorted: every later value is bigger too
path.append(value)
explore(i, remaining - value) # i, not i + 1: this stamp may be reused
path.pop()
explore(0, target)
return resultTwo other details carry the design:
startmeans each branch only uses stamps at or after the current one. So stamps are always added in sorted order, and[2, 3, 3]can never reappear as[3, 2, 3]or[3, 3, 2].explore(i, ...)lets the same stamp be picked again. Passingi + 1instead would allow each value at most once.
Pruning never changes which answers are found, only how much of the tree gets visited. For postage of 8 cents the saving is small, but as the target grows, dead branches vastly outnumber live ones, and pruning is what keeps backtracking usable.
The shortcut
For every backtracking problem, ask three questions before coding: What is one choice? (the next stamp) When is a path complete? (nothing remaining) When is a path hopeless? (the next stamp is too big). The third question is where the speed comes from.
Keep taking 2s
2, 2, 2, 2 brings the remainder to 0: record
[2, 2, 2, 2]. Back at a remainder of 2, the 3 is too big, sobreak.
The trap is writing continue where break belongs, or break on unsorted values. continue is correct but wastes time; break without sorting silently drops real answers.
Drills
Answer fast — trust the rule.
How many combinations does ways_to_total([2, 3, 5], 10) return?
With explore(i + 1, remaining - value) instead, what does ways_to_total([2, 3, 5], 8) return?
If every call looped from 0 instead of from start, what would go wrong?
What does ways_to_total([2, 4], 7) return?
Remember
- Stop a branch the moment it can no longer succeed.
- Shortcut: one choice, complete when, hopeless when; the last one is the speed.
- Trap:
breakon unsorted values, or looping from 0 and getting repeats.