Choose, explore, undo

Recursion that builds something up and takes it apart again. The undo is the whole difference.

Key idea

What backtracking is

Backtracking explores a tree of decisions. At each step you have a set of choices, you take one, you recurse to make the remaining decisions, and then you put things back the way they were and try the next choice.

That last part is what makes it backtracking rather than plain recursion. The state being built is shared across the whole search, so anything a branch changes has to be unchanged before its sibling runs.

1def binary_strings(length):2    results = []3    current = []4 5    def explore():6        if len(current) == length:7            results.append("".join(current))8            return9        for digit in "01":10            current.append(digit)      # choose11            explore()                  # explore12            current.pop()              # undo13    explore()14    return results15 16print(binary_strings(3))

Gotcha

Append a copy, not the list itself

results.append(current) stores a reference to the same list that the search keeps mutating. By the time the search finishes, every stored result points at the same, now empty, list.

Store current[:] or list(current) or "".join(current). Anything that takes a snapshot. This is the single most common backtracking bug and its symptom is distinctive: the right number of results, all identical, usually all empty.

1def broken():2    results, current = [], []3    def explore():4        if len(current) == 2:5            results.append(current)        # reference, not a copy6            return7        for digit in "01":8            current.append(digit)9            explore()10            current.pop()11    explore()12    return results13 14print(broken())

Key idea

A second framing: include or exclude

Some problems are more naturally written as a binary decision per element rather than a loop over choices. Take this element or do not, then move to the next.

Both framings generate the same things and one is usually shorter for a given problem. Being able to switch between them is worth practicing, because a problem that looks awkward in one is often obvious in the other.

Below, each element is either taken or not, and what accumulates is a single number rather than a list. That removes the need for an undo at all: the state travels as a parameter, so nothing has to be put back.

1def subset_sums(items):2    """Every total reachable by taking some of the items."""3    results = []4 5    def explore(index, running):6        if index == len(items):7            results.append(running)8            return9        explore(index + 1, running)                   # exclude items[index]10        explore(index + 1, running + items[index])    # include it11 12    explore(0, 0)13    return results14 15print(subset_sums([1, 2]))

Predict the output· 5 min

Predict the output: forgetting the undo

The pop is missing. The base case uses >= rather than ==, which is the only reason this terminates at all. Type what it prints.

Python

1def broken(length):2    results = []3    current = []4    def explore():5        if len(current) >= length:6            results.append("".join(current))7            return8        for digit in "01":9            current.append(digit)10            explore()11            # no pop12    explore()13    return results14 15print(broken(2))

Printed output

Code lab· 30 min

Template drills

Three searches on the same skeleton. all_paths lists every path from the top-left to the bottom-right of a grid moving only right or down, as strings of R and D. combinations_of lists every way to choose exactly k items from a list, keeping the original order. all_splits lists every way to break a string into non-empty consecutive pieces.

solution.py

Tests

print(sorted(all_paths(2, 2)))print(sorted(all_paths(1, 3)))print(sorted(combinations_of([1, 2, 3], 2)))print(sorted(combinations_of([1, 2], 0)))print(len(all_splits("abc")), sorted(all_splits("ab")))

Output

Run tests to see output.

Problem· 22 min

Subsets

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1def binary_strings(length):2 results = []3 current = []4 5 def explore():6 if len(current) == length:7 results.append("".join(current))8 return9 for digit in "01":10 current.append(digit) # choose11 explore() # explore12 current.pop() # undo13 explore()14 return results15 16print(binary_strings(3))

1def broken():2 results, current = [], []3 def explore():4 if len(current) == 2:5 results.append(current) # reference, not a copy6 return7 for digit in "01":8 current.append(digit)9 explore()10 current.pop()11 explore()12 return results13 14print(broken())

1def subset_sums(items):2 """Every total reachable by taking some of the items."""3 results = []4 5 def explore(index, running):6 if index == len(items):7 results.append(running)8 return9 explore(index + 1, running) # exclude items[index]10 explore(index + 1, running + items[index]) # include it11 12 explore(0, 0)13 return results14 15print(subset_sums([1, 2]))

1def broken(length):2 results = []3 current = []4 def explore():5 if len(current) >= length:6 results.append("".join(current))7 return8 for digit in "01":9 current.append(digit)10 explore()11 # no pop12 explore()13 return results14 15print(broken(2))

print(sorted(all_paths(2, 2)))print(sorted(all_paths(1, 3)))print(sorted(combinations_of([1, 2, 3], 2)))print(sorted(combinations_of([1, 2], 0)))print(len(all_splits("abc")), sorted(all_splits("ab")))