Choose, Explore, Un-choose
One template covers subsets, combinations and permutations.
13 min, 0 of 4 activities solved
View cheatsheetGetting Python ready… examples can run in a moment.
Nearly every backtracking solution has the same three-beat rhythm:
def backtrack(state):
if state is a complete answer:
record a COPY of it
return
for choice in available choices:
if choice breaks a rule: continue
make the choice # choose
backtrack(new state) # explore
undo the choice # un-choose
The state is usually one shared path list that
grows with append and shrinks with pop. That's
what keeps it cheap: no copying on every step, only
when you record an answer.
Subsets with a start index (traced)
This is a different tree from lesson 1: each node
picks which number comes next, and only numbers
after the last one (start = i + 1). That rule
means [2, 1] is never built, so no subset
appears twice. Every node is an answer here, so we
record before the loop.
subsets([1, 2, 3]) with a start index
backtrack(0) records [] before its loop: in this tree every node is a subset, not just the leaves. The loop will offer 1, 2 and 3.
Each edge adds one number, always from the right of the last one (13 means [1, 3]).
This version forgot to copy. What does it print?
Three shapes to memorise. They differ in two places: which choices the loop offers, and when you record.
| Shape | Loop over | Record when | Order matters? |
|---|---|---|---|
| Subsets | range(start, n) |
every node | no |
| Combinations (size k) | range(start, n) |
len(path) == k |
no |
| Permutations | range(n) skipping used |
len(path) == n |
yes |
- Start index → you only look forward, so each group of items is built once, in one order.
- Used set → you may pick any unused item, so
[1, 2]and[2, 1]are both built. That's exactly what permutations want.
Permutations with a used array (traced)
Two pieces of state change (path and used),
so two things are undone. Forgetting
used[i] = False is a classic bug: the number
stays "taken" forever and later branches produce
nothing.
Combinations of size k
Same loop as subsets, just a different base case.
Try changing backtrack(i + 1) to
backtrack(i): now an item can be reused, which
is exactly what "Combination Sum" needs.
How many pairs does this collect?
Why do permutations use a 'used' set instead of a start index?
Combinations of 1..n
Write combine(n, k) that returns every way to
choose k numbers from 1..n, as a list of
lists (any order). Each inner list should be
increasing, like [1, 3], and no combination may
appear twice.
combine(4, 2) →
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
Write the search yourself (no itertools).