Know this before you start: “Prune branches that can't work”
Pruning: stop branches that can't work
Before exploring a choice, check whether it can still lead to an answer. Cutting dead branches early is what makes backtracking fast enough.
The idea
Plain backtracking explores every branch to the end. Most of them are hopeless long before that: the sum is already too big, a queen is already attacked, the word doesn't match.
Check as early as possible and return. Sorting the options often helps: once one option is too big, every later one is too, so you can stop the loop (break), not just skip.
See it step by step
Combinations of [2, 3, 6, 7] adding to 7 (reuse allowed)
- Sorted. Path [2, 2, 2] has 1 left: 2 > 1, so stop the loop there: every later option is bigger too.
- Path [2, 2] + 3 = 7 ✓. Path [7] ✓.
- Answers: [2, 2, 3] and [7], with most dead ends never explored.
In code (Python)
def combination_sum(candidates, target):
candidates.sort()
result, path = [], []
def explore(start, remaining):
if remaining == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
if candidates[i] > remaining:
break # prune: sorted, nothing later fits
path.append(candidates[i])
explore(i, remaining - candidates[i])
path.pop()
explore(0, target)
return result
print(combination_sum([2, 3, 6, 7], 7)) # [[2, 2, 3], [7]]Still exponential in the worst case; much faster in practice.
When you'll use it
- Every backtracking problem: sums, N-Queens (attacked squares), word search (letter mismatch), Sudoku.
Common mistakes
- Checking validity only at the end.
- `continue` where `break` is safe (and faster) after sorting.
