Backtracking: Try, Check, Undo

#Try, Check, Undo: The Big Idea

#Quick Recap: DFS, Trees and Recursion

Backtracking rests on three things you already met. Five lines will do.

1. A recursive function calls itself on a smaller problem, and a base case stops it (Recursion and DP).
2. Each call has its own local variables. Calls pile up on the call stack and finish in reverse order.
3. A tree is a node with child nodes. A depth-first walk goes down one branch before the next (Trees and BST).
4. Depth-first search on a graph does the same and marks nodes as visited (Graphs).
5. Backtracking is a depth-first walk over a tree of choices that we never build. The call stack is the tree.

If any of the five feels shaky, open the linked lesson first.

#The Decision Tree Picture

Here is the tree. Read it from the top. Each line shows a choice and the state it leads to. The word "answer" marks a leaf, where all three decisions are made.

[]                              nothing chosen yet
├─ take 1 -> [1]
│  ├─ take 2 -> [1, 2]
│  │  ├─ take 3 -> [1, 2, 3]    answer
│  │  └─ skip 3 -> [1, 2]       answer
│  └─ skip 2 -> [1]
│     ├─ take 3 -> [1, 3]       answer
│     └─ skip 3 -> [1]          answer
└─ skip 1 -> []
   ├─ take 2 -> [2]
   │  ├─ take 3 -> [2, 3]       answer
   │  └─ skip 3 -> [2]          answer
   └─ skip 2 -> []
      ├─ take 3 -> [3]          answer
      └─ skip 3 -> []           answer

Three levels, eight leaves. The tree is never stored. Your function visits it one node at a time, always going down first. When it reaches a leaf it records the answer, then climbs back up one step and takes the next unexplored branch. Climbing back up is the backtrack.

#Choose, Explore, Un-choose: The Template

Notice rows 4, 6 and 9. After coming back from a branch, the state is put back exactly as it was before the choice. That is the whole trick. Without it, the next branch would start from a dirty state.

The three steps have names:

1. Choose. Add one option to the state.
2. Explore. Call the function again to handle everything that can follow.
3. Un-choose. Remove the option, so the state is as it was.

def subsets(items):
    results = []
    path = []

    def explore(i):
        if i == len(items):
            results.append(path[:])     # a full answer: store a copy of path
            return
        path.append(items[i])           # choose: take items[i]
        explore(i + 1)                  # explore everything that follows
        path.pop()                      # un-choose: put path back as it was
        explore(i + 1)                  # the other choice: skip items[i]

    explore(0)
    return results


for s in subsets([1, 2, 3]):
    print(s)
# Output:
# [1, 2, 3]
# [1, 2]
# [1, 3]
# [1]
# [2, 3]
# [2]
# [3]
# []

The order matches the tree read from the top down. The shape is the same in every problem below: a base case that records an answer, then a loop or a pair of calls, each wrapped in choose and un-choose.

#Subsets

The function above is the subsets solution, so here is what to remember about it.

The answer for n items has one list for every leaf of the tree, and the tree has two branches at each of n levels. So the leaves number 2 multiplied by itself n times, written 2^n. For 3 items that is 8, as the picture showed.

#Permutations

def permutations(items):
    results = []
    path = []
    used = [False] * len(items)

    def explore():
        if len(path) == len(items):
            results.append(path[:])
            return
        for i in range(len(items)):
            if used[i]:
                continue                # this item is already in path
            used[i] = True              # choose
            path.append(items[i])
            explore()                   # explore
            path.pop()                  # un-choose
            used[i] = False

    explore()
    return results


print(permutations(["a", "b", "c"]))
print(len(permutations([0, 1, 2, 3, 4, 5])))
# Output:
# [['a', 'b', 'c'], ['a', 'c', 'b'], ['b', 'a', 'c'], ['b', 'c', 'a'], ['c', 'a', 'b'], ['c', 'b', 'a']]
# 720

This function treats equal items as different. Given [1, 1, 2] it returns 6 lists, with each distinct arrangement twice. The next section shows the standard fix for repeated values.

#Combinations and Duplicates

Real input often has repeated values. Take [1, 2, 2, 3] and choose 2. The two 2s sit at different positions, so a plain version builds [1, 2] twice and [2, 3] twice. The fix has two parts:

1. Sort the items first, so equal values sit side by side.
2. In the loop, if the item at i equals the item at i - 1 and i is not the first pick at this level, skip it.

The second rule says: at the same level of the tree, never try the same value twice. Using a 2 at one level and another 2 at the next level is fine, because that is how you get [2, 2].

def combinations(items, k):
    items = sorted(items)               # equal values must sit side by side
    results = []
    path = []

    def explore(start):
        if len(path) == k:
            results.append(path[:])
            return
        for i in range(start, len(items)):
            if i > start and items[i] == items[i - 1]:
                continue                # same value already tried at this level
            path.append(items[i])       # choose
            explore(i + 1)              # explore
            path.pop()                  # un-choose

    explore(0)
    return results


print(combinations([1, 2, 3, 4], 2))
print(combinations([1, 2, 2, 3], 2))
# Output:
# [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
# [[1, 2], [1, 3], [2, 2], [2, 3]]

The count of answers is "n choose k", written C(n, k). For 4 items and k = 2 that is 6. The tree has one node for every forward-only selection of up to k items. When k is at most half of n, that is about k times C(n, k) nodes at most, so time is O(k * C(n, k)). Repeated values only remove branches. Extra space is O(k).

#Combination Sum

def combination_sum(candidates, target):
    candidates = sorted(candidates)
    results = []
    path = []

    def explore(start, remaining):
        if remaining == 0:
            results.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break                           # sorted: every later one is too big too
            path.append(candidates[i])          # choose
            explore(i, remaining - candidates[i])   # i, not i + 1: reuse is allowed
            path.pop()                          # un-choose

    explore(0, target)
    return results


print(combination_sum([2, 3, 6, 7], 7))
print(combination_sum([2, 3, 5], 8))
# Output:
# [[2, 2, 3], [7]]
# [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

#Pruning: Cut the Branch Early

def count_calls(candidates, target, prune):
    candidates = sorted(candidates)
    calls = 0

    def explore(start, remaining):
        nonlocal calls
        calls += 1
        if remaining <= 0:
            return
        for i in range(start, len(candidates)):
            if prune and candidates[i] > remaining:
                break
            explore(i, remaining - candidates[i])

    explore(0, target)
    return calls


for candidates, target in ([2, 3, 6, 7], 7), ([2, 3, 5], 8):
    print(candidates, target, count_calls(candidates, target, False), count_calls(candidates, target, True))
# Output:
# [2, 3, 6, 7] 7 28 10
# [2, 3, 5] 8 23 13

For the first input the pruned search makes 10 calls and the unpruned search makes 28. Both find the same answers. Only the dead ends differ.

The rule for good pruning: check a constraint as early as you can, ideally before you make the choice, and only prune when the check is certain. A prune that removes a branch holding a real answer is a bug, not an optimisation.

Pruning does not change the worst case. An input can be built so that no branch can be cut until the very end. What it changes is the typical case, and for puzzles with strong rules the typical case is the difference between a second and a lifetime. The next section shows that with numbers.

#N-Queens

def solve_queens(n):
    solutions = []
    cols_of_row = []                    # cols_of_row[r] is the column of the queen in row r
    cols, diag_down, diag_up = set(), set(), set()

    def explore(row):
        if row == n:
            solutions.append(cols_of_row[:])
            return
        for col in range(n):
            if col in cols or (row - col) in diag_down or (row + col) in diag_up:
                continue                # attacked: prune this branch
            cols.add(col)               # choose
            diag_down.add(row - col)
            diag_up.add(row + col)
            cols_of_row.append(col)
            explore(row + 1)            # explore
            cols_of_row.pop()           # un-choose
            cols.remove(col)
            diag_down.remove(row - col)
            diag_up.remove(row + col)

    explore(0)
    return solutions


solutions = solve_queens(4)
print(solutions)
for col in solutions[0]:
    print("".join("Q" if c == col else "." for c in range(4)))
print([len(solve_queens(n)) for n in range(1, 9)])
# Output:
# [[1, 3, 0, 2], [2, 0, 3, 1]]
# .Q..
# ...Q
# Q...
# ..Q.
# [1, 0, 0, 2, 10, 4, 40, 92]

For n = 2 and n = 3 there is no solution at all, and the function correctly returns an empty list. For n = 8 there are 92.

import math


def count_explore_calls(n):
    calls = 0
    cols, diag_down, diag_up = set(), set(), set()

    def explore(row):
        nonlocal calls
        calls += 1
        if row == n:
            return
        for col in range(n):
            if col in cols or (row - col) in diag_down or (row + col) in diag_up:
                continue
            cols.add(col); diag_down.add(row - col); diag_up.add(row + col)
            explore(row + 1)
            cols.remove(col); diag_down.remove(row - col); diag_up.remove(row + col)

    explore(0)
    return calls


for n in (4, 6, 8):
    full_tree = sum(math.perm(n, k) for k in range(n + 1))
    print(n, count_explore_calls(n), full_tree)
# Output:
# 4 17 65
# 6 153 1957
# 8 2057 109601

For 8 queens the pruned search makes 2,057 calls. The full permutation tree has 109,601 nodes. Placing 8 queens on any 8 of the 64 squares would be 4,426,165,368 choices. The rules do the cutting for us.

The worst-case time is O(n!), since no search can have more nodes than the permutation tree, and in practice it is far less. Extra space is O(n): three sets and a list, each at most n long, plus a stack n deep.

#Word Search on a Grid

Now a grid. You get a board of letters and a word. Can you spell the word by walking from cell to cell, moving up, down, left or right, without using the same cell twice?

The state is the current cell and how many letters of the word are matched. The choices are the four neighbours. The pruning is free: if the cell's letter is wrong, stop at once.

def word_search(grid, word):
    rows, cols = len(grid), len(grid[0])

    def explore(r, c, k):
        if k == len(word):
            return True                       # every letter matched
        if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != word[k]:
            return False                      # off the board, or the wrong letter
        saved = grid[r][c]
        grid[r][c] = "#"                      # choose: mark this cell as used
        found = (explore(r + 1, c, k + 1) or explore(r - 1, c, k + 1)
                 or explore(r, c + 1, k + 1) or explore(r, c - 1, k + 1))
        grid[r][c] = saved                    # un-choose: put the letter back
        return found

    return any(explore(r, c, 0) for r in range(rows) for c in range(cols))


grid = [list("ABCE"), list("SFCS"), list("ADEE")]
for w in ("ABCCED", "SEE", "ABCB"):
    print(w, word_search(grid, w))
print(grid)
# Output:
# ABCCED True
# SEE True
# ABCB False
# [['A', 'B', 'C', 'E'], ['S', 'F', 'C', 'S'], ['A', 'D', 'E', 'E']]

Let L be the length of the word. After the first letter, each step has at most 3 new neighbours, because the cell you came from is marked. Time is O(R * C * 3^L) for a board with R rows and C columns, since any cell can start a path. The looser textbook bound is 4^L. Extra space is O(L) for the call stack.

#The Sudoku Idea

Sudoku is N-Queens with a different rule. You fill empty cells with digits so that no digit repeats in a row, a column or a box. The backtracking solver does the following:

1. Find the first empty cell. If there is none, the board is solved.
2. Try each digit that does not break a rule (choose).
3. Solve the rest of the board (explore).
4. If the rest cannot be solved, erase the digit (un-choose) and try the next one.
5. If no digit fits, return failure, so the caller backs up.

Here is the whole idea on a 4 by 4 board with 2 by 2 boxes, using digits 1 to 4. A 9 by 9 board uses the same code with bigger ranges. A zero means empty. This function returns True or False, because we want one solution, not all of them, and we stop at the first.

def solve_sudoku4(board):
    def fits(r, c, v):
        if v in board[r]:
            return False
        if any(board[i][c] == v for i in range(4)):
            return False
        br, bc = r // 2 * 2, c // 2 * 2         # top-left corner of the 2 by 2 box
        return all(board[br + i][bc + j] != v for i in range(2) for j in range(2))

    def explore():
        for r in range(4):
            for c in range(4):
                if board[r][c] == 0:
                    for v in (1, 2, 3, 4):
                        if fits(r, c, v):
                            board[r][c] = v         # choose
                            if explore():           # explore
                                return True
                            board[r][c] = 0         # un-choose
                    return False                    # no digit fits: back up
        return True                                 # no empty cell is left

    return explore()


puzzle = [[1, 0, 0, 0],
          [0, 0, 3, 0],
          [0, 4, 0, 0],
          [0, 0, 0, 2]]
print(solve_sudoku4(puzzle))
for row in puzzle:
    print(row)
# Output:
# True
# [1, 3, 2, 4]
# [4, 2, 3, 1]
# [2, 4, 1, 3]
# [3, 1, 4, 2]

The cost is at most 4 to the power of the number of empty cells for this board, or 9 to the power of the empty cells for a 9 by 9 board. That is a huge ceiling. Real sudokus solve fast because the rules prune almost every branch. Extra space is O(cells) for the stack.

#Counting the Work Honestly

We have said "2^n" and "n!" several times. Now see how big they get. First a prediction.

This table was printed by code. Both columns grow without any mercy, and the second grows faster.

import math

for n in (5, 10, 15, 20):
    print(f"{n:>2} {2**n:>10,} {math.factorial(n):>27,}")
# Output:
#  5         32                         120
# 10      1,024                   3,628,800
# 15     32,768           1,307,674,368,000
# 20  1,048,576   2,432,902,008,176,640,000

Twenty items is not much, and yet listing all their permutations is out of reach: at a billion answers per second it takes about 77 years. Doubling n in a polynomial algorithm costs a few times more. Adding one item to a factorial search multiplies the work by n plus 1.

So here is the honest summary:

• Listing every subset is O(2^n) answers, and listing every arrangement is O(n!). No code can list them faster, because the output itself is that long.
• Pruning cuts the typical cost a great deal. It rarely cuts the worst case.
• Backtracking is practical when n is small (about 20 for subsets, about 10 for permutations) or when the rules prune hard, as in N-Queens and sudoku.

When is backtracking the only option? Some problems have no known fast method. "Is there a subset of these numbers that adds up to exactly this target?" and "can this huge sudoku be completed?" belong to a family called NP-hard. Nobody has found an algorithm for them whose cost grows only polynomially, and most experts believe none exists.

For them, a pruned search or a clever approximation is the standard tool. A later lesson in this part, on NP-hardness, tells that story properly. For now, remember that exponential cost is not always a flaw in your code. It can be the nature of the question.

#Backtracking or Dynamic Programming?

Both tools split a problem into smaller choices. How do you pick? Ask one question: does the same sub-question come back again and again?

Count how many subsets of the numbers 1 to 20 add up to 50, with plain backtracking and then with a cache. The cache key is the pair (i, remaining).

from functools import lru_cache

items = list(range(1, 21))
target = 50


def count_plain(i, remaining):
    global calls
    calls += 1
    if remaining == 0:
        return 1
    if i == len(items) or remaining < 0:
        return 0
    return count_plain(i + 1, remaining - items[i]) + count_plain(i + 1, remaining)


calls = 0
print(count_plain(0, target), calls)


@lru_cache(maxsize=None)
def count_cached(i, remaining):
    if remaining == 0:
        return 1
    if i == len(items) or remaining < 0:
        return 0
    return count_cached(i + 1, remaining - items[i]) + count_cached(i + 1, remaining)


print(count_cached(0, target), count_cached.cache_info().misses)
# Output:
# 1969 172493
# 1969 886

Both give 1,969. The plain version makes 172,493 calls. The cached version solves only 886 distinct states. With a cache, the cost is at most n times target states, with O(1) work each, so O(n * target) time and space. That is a pseudo-polynomial bound: it grows with the size of the target number, not just the number of items.

Now the catch. The cached version returns a count. It cannot give you the 1,969 subsets themselves, since the cache has forgotten which path made each one. And for permutations the state is the whole arrangement so far, so no two paths meet, and there is nothing to share.

Use this rule of thumb:

A good habit is to write the backtracking first, because it is easiest to get right. Then ask whether the state repeats. If it does and the question wants a count or a best value, add a cache.

#An Aside: Generators with yield

import itertools


def permutations_gen(items):
    path = []
    used = [False] * len(items)

    def explore():
        if len(path) == len(items):
            yield tuple(path)
            return
        for i in range(len(items)):
            if used[i]:
                continue
            used[i] = True
            path.append(items[i])
            yield from explore()        # pass up every answer from below
            path.pop()
            used[i] = False

    yield from explore()


gen = permutations_gen("abcd")
print(next(gen))
print(next(gen))
print(sum(1 for _ in permutations_gen(range(7))))
print(list(permutations_gen("abc")) == list(itertools.permutations("abc")))
print(next(permutations_gen(range(12))))
# Output:
# ('a', 'b', 'c', 'd')
# ('a', 'b', 'd', 'c')
# 5040
# True
# (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)

The last line asks for the first of 12! permutations and gets it at once, because nothing else has been built. Total time to walk all of them is the same as before. Extra space drops to O(n), because only the current path is held.

#Common Mistakes

Before the first mistake, predict what Python does with two names for one list.

#Try It: The Five-Problem Ladder

Five problems, from easy to hard. Each one uses the template with one new twist. Fill in each TODO and run. All results are sorted before they print, so a correct answer always prints the same text. Stuck for fifteen minutes on a rung? Open the solution, read only that function, close it and rewrite it.

1. Subsets with a given sum: the lesson's subsets with one extra check at the leaf.
2. Arrangements of k letters: permutations that stop early.
3. Balanced brackets: pruning while you build the text.
4. Find the bugs: a subsets function with two of the mistakes above.
5. Faster N-Queens: replace an O(n) safety scan with three sets, and say the new cost.

Costs for the ladder, with reasons. Problem 1 is O(n * 2^n) time, as in subsets, and O(n) extra space. Problem 2 is O(k * n!/(n-k)!) time, because the tree has that many leaves of depth k, and O(k) space. Problem 3 is exponential time, because the number of answers grows toward 4 times larger for every extra pair, and O(n) space beyond the output. Problem 5 is O(n!) time at worst, with each check O(1) now, and O(n) space.

#Recap

Backtracking builds an answer one choice at a time, checks the rules early, and undoes each choice on the way back. Every problem here is the same three steps: choose, explore, un-choose. The decision tree shows the shape of the search, and the call stack is that tree.

Subsets take or skip each item, with 2^n leaves. Permutations pick any unused item, with n! leaves, and combinations only move forward. Sorting plus a same-level skip rule handles repeated values. N-Queens uses three sets, word search marks cells in place, and sudoku is the same loop with a different rule.