Choose, Explore, Un-choose

Backtracking, lesson 2 of 3

Choose, Explore, Un-choose

One template covers subsets, combinations and permutations.

13 min, 0 of 4 activities solved

Getting 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.

Example

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.

Quiz

This version forgot to copy. What does it print?

[[], [], [], [], [], [], [], []]

[[], [0], [0, 1], [0, 1, 2], [0, 2], [1], [1, 2], [2]]

[[0, 1, 2]]

[]

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.

Example

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.

Example

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.

Quiz

How many pairs does this collect?

10

20

25

5

Quiz

Why do permutations use a 'used' set instead of a start index?

Because [2, 1] must be built too, so the loop has to look back at earlier items that aren't taken yet

Because a start index would make the search slower

Because permutations can't contain duplicates

Because recursion depth would be too large with a start index

Exercise

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).