Backtracking

What backtracking is

Some problems ask you to build an answer out of a series of small choices. “Pick some of these numbers.” “Arrange these letters in every possible order.” “Place eight queens on a chessboard so none attacks another.” In each one you make a choice, then another, then another, until you either have a complete answer or you hit a dead end.

Backtracking is a way of exploring all of those choice sequences without getting lost. You build a solution one choice at a time. After each choice you ask, can this partial solution still lead somewhere valid? If yes, you keep going deeper. If no, or if you have exhausted the options at this point, you undo the last choice and try a different one. Undoing a choice and stepping back is where the name comes from: you back up and track a different route.

A few terms first, since the reader may be new to all of this.

• A function is a named block of code you run by writing its name and parentheses. It can call itself; that is recursion, and backtracking is built on it.
• A list is Python’s ordered, growable sequence, written [1, 2, 3]. path.append(x) adds x to the end; path.pop() removes and returns the last item.
• A partial solution is an answer that is not finished yet: some choices made, more still to make.
• To prune means to cut off a whole branch of possibilities early because you can already tell it cannot work, so you never bother exploring it.

The template: choose, explore, un-choose

Almost every backtracking solution has the same three-step shape inside a recursive function.

1. Choose: add one option to the current partial solution.
2. Explore: recurse to make the next choice on top of it.
3. Un-choose: remove the option you just added, restoring the partial solution to exactly what it was before, so the next option starts from a clean state.

Here is the skeleton in plain form:

def backtrack(path, choices):
    if is_complete(path):        # a full solution
        record(path)
        return
    for option in choices:
        if not allowed(option, path):
            continue             # prune: skip options that cannot work
        path.append(option)      # 1. choose
        backtrack(path, choices) # 2. explore
        path.pop()               # 3. un-choose

The path.pop() on the last line is the single most important line in backtracking. It is the “un-choose”. If you forget it, every branch leaks its choices into the next one, corrupting all later results. We will see exactly why below.

First worked example: all subsets

A subset of a list is any selection of its items, including the empty selection and the whole list. For [1, 2, 3] there are eight subsets: [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3].

The choice at each position is binary: for each number, either include it or skip it. We walk the list index by index. At each index we make both choices, one after the other.

def subsets(nums):
    result = []
    path = []

    def backtrack(start):
        result.append(path[:])       # record a copy of the current subset
        for i in range(start, len(nums)):
            path.append(nums[i])     # choose nums[i]
            backtrack(i + 1)         # explore with later items only
            path.pop()               # un-choose

    backtrack(0)
    return result

print(subsets([1, 2, 3]))
# -> [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

Two details matter. First, path[:] makes a copy of the list. If you appended path itself, every entry in result would point at the same list object, and after the final pops they would all show as []. Second, backtrack(i + 1) passes i + 1, not start, so each item is only ever combined with items that come after it. That is what prevents [1, 2] and [2, 1] from both appearing; order does not matter in a subset.

The whole search is easiest to hold in your head as a tree of partial solutions. Each node is a value of path at some moment. Each edge (arrow) is one “choose” step deeper; every arrow is later undone by a matching “un-choose” as the recursion returns. Here is that tree for subsets([1, 2, 3]):

flowchart TD
    R["[]"] --> A["[1]"]
    R --> B["[2]"]
    R --> C["[3]"]
    A --> A1["[1, 2]"]
    A --> A2["[1, 3]"]
    A1 --> A11["[1, 2, 3]"]
    B --> B1["[2, 3]"]

Read it top to bottom, left to right. Starting from [] we choose 1, then from [1] we choose 2, then 3, reaching [1, 2, 3]. We then un-choose back up to [1] and try 3 instead, giving [1, 3]. Every node in the tree is one of the eight subsets, and the order the nodes are first reached is exactly the printed order above.

Step-by-step trace

Here is the mechanism line by line for subsets([1, 2, 3]). “Action” is the operation just performed; the other columns show the state right after it. result is shown as it grows.

Notice how path always returns to exactly its earlier state after a subtree finishes. That is the un-choose doing its job.

Complexity

There are 2**n subsets for n items, because each item is independently in or out. Building each one costs up to O(n) to copy the path. So the time is O(n * 2**n), which is also the size of the output. The space, not counting the output, is O(n): the recursion goes at most n levels deep, and path holds at most n items. There is no way to beat 2**n here because there are genuinely that many answers to produce.

Second worked example: all permutations

A permutation is an arrangement of all the items in a specific order. For [1, 2, 3] there are six: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]. Unlike subsets, order matters and every item must be used exactly once.

The choice at each step is: which unused item goes in the next position? We track which items are still available.

def permutations(nums):
    result = []
    path = []
    used = [False] * len(nums)   # used[i] is True once nums[i] is placed

    def backtrack():
        if len(path) == len(nums):   # all positions filled
            result.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue             # prune: this item is already placed
            used[i] = True           # choose
            path.append(nums[i])
            backtrack()              # explore
            path.pop()               # un-choose
            used[i] = False          # un-choose the "used" mark too

    backtrack()
    return result

print(permutations([1, 2, 3]))
# -> [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

The if used[i]: continue line is a prune. It skips any item already sitting in path, so we never try to use the same item twice. Note that this function undoes two pieces of state on the way back up: it pops from path and resets used[i] to False. Any state you change on the way down must be restored on the way up, without exception.

Drawn the same way, permutations([1, 2, 3]) branches like this:

flowchart TD
    R["[]"] --> A["[1]"]
    R --> B["[2]"]
    R --> C["[3]"]
    A --> A1["[1, 2]"]
    A --> A2["[1, 3]"]
    A1 --> A11["[1, 2, 3]"]
    A2 --> A21["[1, 3, 2]"]
    B --> B1["[2, 1]"]
    B --> B2["[2, 3]"]
    B1 --> B11["[2, 1, 3]"]
    B2 --> B21["[2, 3, 1]"]
    C --> C1["[3, 1]"]
    C --> C2["[3, 2]"]
    C1 --> C11["[3, 1, 2]"]
    C2 --> C21["[3, 2, 1]"]

The tree is wider than the subset tree: at the top level all three items are available, at the next level two remain, then one. The leaf nodes at the bottom (the six three-item lists) are the answers. A leaf is a node with no children, here meaning a completed permutation.

Complexity

There are n! (n factorial: n * (n-1) * ... * 1) permutations, and copying each costs O(n), so time is O(n * n!). Space excluding the output is O(n) for the recursion depth plus the used array. 6 permutations for n = 3 feels small, but 10! = 3,628,800 and 13! is over six billion. Backtracking explores real work; it does not make an exponential problem cheap.

Pruning: cutting branches early

The prunes above (continue on a used item) skip single options. The bigger win comes when one early choice makes an entire subtree impossible, and you cut all of it at once. The classic example is N-Queens.

N-Queens sketch

Place N queens on an N x N chessboard so that no two share a row, column, or diagonal. We place one queen per row, top to bottom. For each row we try each column. Before committing, we check the queen against all already-placed queens; if it conflicts, we prune that column and never recurse into it.

def solve_n_queens(n):
    result = []
    cols = [-1] * n              # cols[r] = column of the queen in row r

    def safe(row, col):
        for r in range(row):     # check queens already placed above
            c = cols[r]
            if c == col:                       # same column
                return False
            if abs(c - col) == abs(r - row):   # same diagonal
                return False
        return True

    def backtrack(row):
        if row == n:             # placed a queen in every row
            result.append(cols[:])
            return
        for col in range(n):
            if not safe(row, col):
                continue         # prune: this placement attacks another queen
            cols[row] = col      # choose
            backtrack(row + 1)   # explore
            cols[row] = -1       # un-choose

    backtrack(0)
    return result

print(len(solve_n_queens(4)))   # -> 2
print(solve_n_queens(4))        # -> [[1, 3, 0, 2], [2, 0, 3, 1]]

Each result like [1, 3, 0, 2] reads “row 0 queen in column 1, row 1 in column 3, row 2 in column 0, row 3 in column 2.” The safe check is the prune, and it is doing enormous work: without it we would examine 4**4 = 256 placements for the 4x4 board; with it, most rows have only a couple of viable columns, so the search collapses to a handful of paths.

This tree shows pruning concretely for the first two rows of the 4x4 board. Nodes marked pruned fail the safe check and are never expanded; the search never visits their children.

flowchart TD
    R["row 0"] --> C0["col 0"]
    R --> C1["col 1"]
    R --> C2["col 2"]
    R --> C3["col 3"]
    C0 --> C0a["row1 col0 pruned (same col)"]
    C0 --> C0b["row1 col1 pruned (diagonal)"]
    C0 --> C0c["row1 col2 ok"]
    C0 --> C0d["row1 col3 ok"]
    C1 --> C1a["row1 col3 ok"]
    C1 --> C1x["cols 0,1,2 pruned"]

Under col 0 in row 0, two of the four columns in row 1 are killed immediately. Each pruned node stands for a whole subtree, dozens of full-board arrangements, thrown away with one cheap test. That is why backtracking with good pruning can solve boards that a blind enumeration of all N**N placements never could.

Why the complexity is exponential, and how pruning helps

Backtracking explores a tree of choices. If there are b options at each of d levels, the tree has up to b**d nodes; that is exponential growth, meaning the count multiplies rather than adds as the problem grows. Subsets gave 2**n, permutations n!, N-Queens roughly N**N before pruning. These numbers explode fast, and no amount of cleverness changes that when the answer set is genuinely that large (all 2**n subsets really do exist).

Pruning does not change the worst-case Big-O, but it changes the practical running time dramatically. Every branch you cut removes its entire subtree from the search. For N-Queens the difference between N**N and the pruned search is the difference between impossible and instant for boards of a dozen queens. The lesson: pick the strongest, cheapest check you can apply as early as possible, so you reject bad partial solutions before, not after, sinking work into them.

Common pitfalls

• Forgetting to un-choose. If you path.append(x) and recurse but never path.pop(), every sibling branch inherits x. Results become wrong and grow without bound. The pop must run on every path out of the recursive call, which is why it sits right after the recursive call, not inside an if.
• Restoring only some of the state. In the permutation and N-Queens code, more than one variable changes on the way down (path and used; cols). Every one must be undone on the way up. Undoing path but leaving used[i] = True silently drops valid answers.
• Storing the live list instead of a copy. result.append(path) stores a reference to the one list that keeps mutating. After the search finishes, every stored entry reflects the final state of path (often empty), not the moment you recorded it. Always store path[:] or list(path) or tuple(path).
• Shared mutable state across calls. A mutable default argument (def f(path=[])) is created once and reused across every call, so state leaks between independent runs. Create fresh state inside the function, or pass it explicitly.
• Weak or missing base case. As with all recursion, if the “complete” condition is wrong the search either never records answers or never stops. Check the base case first, before the loop.

Practice

1. Write combinations(nums, k) that returns every subset of exactly length k. Start from the subsets function and add a base case that records path only when len(path) == k; prune branches that can no longer reach length k.
2. Modify permutations so it works when nums contains duplicates (for example [1, 1, 2]) and returns each distinct arrangement only once. Hint: sort first, then skip an option if it equals the previous option and that previous option is currently unused.
3. Write letter_combinations(digits) for phone-keypad text entry, where 2 maps to "abc", 3 to "def", and so on. Given "23" it should produce ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. Use the choose / explore / un-choose template with a string or list path.