Backtracking: Choose, Explore, Undo

22 min · Intermediate

Some problems ask for every valid answer: all codes, all teams, all routes. You build each answer one choice at a time. When a path is finished or stuck, you take the last choice back and try the next one. That pattern is backtracking.

Choose, explore, undo

Backtracking is a way to build answers one choice at a time. After exploring a choice you undo it and try the next one, so every possibility is visited once.

A lock has 2 digits, each 0 or 1. List every code. Pick a digit, go one level deeper, then take the digit back and try the other one.

Python

1def codes(path, length):2    if len(path) == length:3        print("".join(path))4        return5    for digit in "01":6        path.append(digit)       # choose7        codes(path, length)      # explore8        path.pop()               # undo9
10
11codes([], 2)

Example 1 · All codes of length 3

Python

1def codes(length):2    results = []3
4    def walk(path):5        if len(path) == length:6            results.append("".join(path))7            return8        for digit in "01":9            path.append(digit)10            walk(path)11            path.pop()12
13    walk([])14    return results15
16
17print(codes(3))

Output

['000', '001', '010', '011', '100', '101', '110', '111']

What this code does

The inner function walk reaches results and length from the outer function, so they need no extra arguments.
Eight codes appear because 2 choices at 3 levels give 2 x 2 x 2 leaves.
The outer function returns a fresh list on every call, so nothing is shared between calls.

path is one list shared by every call. append chooses a digit and pop takes it back, so the list is exactly as before when the next digit is tried.

The search is a tree

Decision tree is a drawing of every choice as a branch. The root is the empty answer, each level adds one more choice, and the leaves are the finished answers.

Every call is a node. Every choice is a branch. A finished answer sits at a leaf. The loop and the recursion together walk the whole tree, left branch first.

Python

1def trace(path, length, depth=0):2    print("  " * depth + "at", path)3    if len(path) == length:4        return5    for digit in "01":6        path.append(digit)7        trace(path, length, depth + 1)8        path.pop()9
10
11trace([], 2)

A tree for codes of length 2. The root is the empty path. Branches 0 and 1 lead to paths 0 and 1, and each of those branches again to leaves 00, 01, 10 and 11. Numbers show the visit order from 1 to 7, going down to a leaf and back up.

Example 2 · Watch the path grow and shrink

Python

1def walk(path, length):2    if len(path) == length:3        return4    for letter in "ab":5        path.append(letter)6        print("enter", "".join(path))7        walk(path, length)8        print("leave", "".join(path))9        path.pop()10
11
12walk([], 2)

Output

enter a
enter aa
leave aa
enter ab
leave ab
leave a
enter b
enter ba
leave ba
enter bb
leave bb
leave b

What this code does

Each enter line is a choice and each leave line is its undo, printed just before pop.
After leave aa the path is a again, and the loop tries b.
Every path appears once as enter and once as leave.

The indentation shows the depth. The answers are the lines at the deepest level.

Save a copy, not the path

Shared state is data that every recursive call can reach and change, such as one path list. It saves memory, but each change must be undone before the next choice is tried.

To keep answers in a list, copy the path first. The path keeps changing, so saving it directly saves the same list again and again.

Python

1results = []2
3
4def walk(path, length):5    if len(path) == length:6        results.append(path[:])    # a copy7        return8    for digit in "01":9        path.append(digit)10        walk(path, length)11        path.pop()12
13
14walk([], 2)15print(results)

Example 3 · The copy bug

Python

1bad, good = [], []2
3
4def walk(path, length):5    if len(path) == length:6        bad.append(path)7        good.append(path[:])8        return9    for digit in "01":10        path.append(digit)11        walk(path, length)12        path.pop()13
14
15walk([], 2)16print(bad)17print(good)

Output

[[], [], [], []]
[['0', '0'], ['0', '1'], ['1', '0'], ['1', '1']]

What this code does

bad holds four references to the one shared list, which is empty at the end.
good holds four separate copies made at the right moment.
If your answers come out empty or all equal, look for a missing copy first.

Without [:] every item in results would be the same list, and it ends up empty after the last pop. list(path) also makes a copy.

The cost: count the leaves

With 2 choices at each of n levels there are 2 to the power n leaves. The extra memory is only the depth n, because the path is one list. Answers grow fast, so keep n small.

Python

1def count(depth, n):2    if depth == n:3        return 14    return 1 + 2 * count(depth + 1, n)5
6
7print(count(0, 10))

Example 4 · Leaves and calls as n grows

Python

1def count(depth, n):2    if depth == n:3        return 14    return 1 + 2 * count(depth + 1, n)5
6
7for n in range(1, 6):8    print(f"n={n} leaves={2 ** n} calls={count(0, n)}")

Output

n=1 leaves=2 calls=3
n=2 leaves=4 calls=7
n=3 leaves=8 calls=15
n=4 leaves=16 calls=31
n=5 leaves=32 calls=63

What this code does

Leaves double with every level, and the calls are one less than twice the leaves.
Doubling is why backtracking only works for small inputs unless you prune.

Example 5 · itertools does it in one line

Python

from itertools import product
words = ["".join(p) for p in product("abc", repeat=2)]print(words)print(len(words))

Output

['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']
9

What this code does

product("abc", repeat=2) gives every pair, the same as two nested loops.
Use it when every position can take any value, whatever the other positions hold.
Write the recursion yourself when a choice depends on the earlier ones.

Example 6 · A choice that depends on earlier ones

Python

1def words(length):2    results = []3
4    def walk(path):5        if len(path) == length:6            results.append("".join(path))7            return8        for letter in "abc":9            if path and path[-1] == letter:10                continue11            path.append(letter)12            walk(path)13            path.pop()14
15    walk([])16    return results17
18
19print(words(3))

Output

['aba', 'abc', 'aca', 'acb', 'bab', 'bac', 'bca', 'bcb', 'cab', 'cac', 'cba', 'cbc']

What this code does

The continue skips a letter equal to the previous one, so those branches are never explored.
product cannot do this, which is the reason to learn the template.
There are 3 x 2 x 2 = 12 words, not 27.

count returns the number of calls. For n = 10 there are 1024 leaves and 2047 calls in total.

Next step

Check your understanding

11 quick questions

1def codes(path, length):2 if len(path) == length:3 print("".join(path))4 return5 for digit in "01":6 path.append(digit) # choose7 codes(path, length) # explore8 path.pop() # undo9 10 11codes([], 2)

1def codes(length):2 results = []3 4 def walk(path):5 if len(path) == length:6 results.append("".join(path))7 return8 for digit in "01":9 path.append(digit)10 walk(path)11 path.pop()12 13 walk([])14 return results15 16 17print(codes(3))

The search is a tree

Decision tree is a drawing of every choice as a branch. The root is the empty answer, each level adds one more choice, and the leaves are the finished answers.

Every call is a node. Every choice is a branch. A finished answer sits at a leaf. The loop and the recursion together walk the whole tree, left branch first.

1def trace(path, length, depth=0):2 print(" " * depth + "at", path)3 if len(path) == length:4 return5 for digit in "01":6 path.append(digit)7 trace(path, length, depth + 1)8 path.pop()9 10 11trace([], 2)

1def walk(path, length):2 if len(path) == length:3 return4 for letter in "ab":5 path.append(letter)6 print("enter", "".join(path))7 walk(path, length)8 print("leave", "".join(path))9 path.pop()10 11 12walk([], 2)

Save a copy, not the path

Shared state is data that every recursive call can reach and change, such as one path list. It saves memory, but each change must be undone before the next choice is tried.

To keep answers in a list, copy the path first. The path keeps changing, so saving it directly saves the same list again and again.

1results = []2 3 4def walk(path, length):5 if len(path) == length:6 results.append(path[:]) # a copy7 return8 for digit in "01":9 path.append(digit)10 walk(path, length)11 path.pop()12 13 14walk([], 2)15print(results)

1bad, good = [], []2 3 4def walk(path, length):5 if len(path) == length:6 bad.append(path)7 good.append(path[:])8 return9 for digit in "01":10 path.append(digit)11 walk(path, length)12 path.pop()13 14 15walk([], 2)16print(bad)17print(good)

1def words(length):2 results = []3 4 def walk(path):5 if len(path) == length:6 results.append("".join(path))7 return8 for letter in "abc":9 if path and path[-1] == letter:10 continue11 path.append(letter)12 walk(path)13 path.pop()14 15 walk([])16 return results17 18 19print(words(3))