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

View cheatsheet

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.

Walkthrough

subsets([1, 2, 3]) with a start index

+1+2+3+3+2+3+3[]112123132233
Step 1 of 8
path = []
start = 0

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.

current path
recorded

Each edge adds one number, always from the right of the last one (13 means [1, 3]).

Quiz

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

Quiz

Why do permutations use a 'used' set instead of 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).