Backtracking cheat sheet

Count the picks that hit an exact total

Walk the items in order and, for each, branch into 'take it' and 'skip it'. Stop a branch as soon as the running total equals the goal (count it) or passes it (prune it). Without pruning this is O(2ⁿ) time with O(n) recursion depth; pruning cuts that sharply on real inputs. For large goals with small prices, a DP table over totals is faster.

def count_picks(prices: list[int], goal: int) -> int:
    def walk(i: int, total: int) -> int:
        if total == goal:
            return 1  # adding more positive prices only overshoots
        if total > goal or i == len(prices):
            return 0  # pruned or out of items
        take = walk(i + 1, total + prices[i])
        return take + walk(i + 1, total)
    return walk(0, 0)

Every order of a playlist

Build orderings one position at a time: try each unused song in the next slot, recurse, then undo. Sorting the ids first makes the output come out in sorted order with no extra sort. There are n! orderings of length n, so O(n · n!) time is the best possible. Apart from the output, the path and flags take O(n) space.

Every selection from a set of toppings

Grow selections in sorted order: record the current path, then for each later item add it, recurse from the next index, and remove it. Every path is recorded once, giving all 2ⁿ selections with no repeats, already in sorted order. O(n · 2ⁿ) time to write them out. Apart from the output, the path takes O(n) space.

def all_selections(toppings: list[int]) -> list[list[int]]:
    items = sorted(toppings)
    path: list[int] = []
    out: list[list[int]] = []

    def grow(start: int) -> None:
        out.append(path[:])  # every partial pick is an answer
        for i in range(start, len(items)):
            path.append(items[i])
            grow(i + 1)  # later items only, so no repeats
            path.pop()

    grow(0)
    return out

Every team of k from n players

Same as listing selections, but record only at size k and stop growing once there. A useful prune: stop the loop when too few players remain to fill the team. There are C(n, k) teams, each of length k, so O(k · C(n, k)) time. Apart from the output, the path takes O(k) space.

Every balanced string of n bracket pairs

Build the string one character at a time with two counters. Add '(' while fewer than n are used; add ')' only while it would not close more than were opened. Every branch then ends in a valid string, so no checking is needed. Trying '(' first gives sorted output. The count is the n-th Catalan number, about 4ⁿ / n^1.5, and each string has 2n characters, so writing them out is O(4ⁿ/√n) time; the recursion is O(n) deep.

Trace a word through a letter grid

Start a depth-first search from every cell that matches the first letter. At each step, mark the cell used, try the four neighbours for the next letter, then unmark it. A branch stops as soon as a letter does not match. Worst case O(R · C · 3^L) for a word of length L, since each step has at most three unused directions. The recursion and the used set take O(L) space.

Cut a word into pieces that each read the same backwards

Try every first piece that reads the same backwards, then recurse on the rest of the word. Shorter first pieces come first, which yields sorted output. There can be 2ⁿ⁻¹ cuttings of length up to n (for 'aaaa…'), so O(n · 2ⁿ) is the worst case, and apart from the output the recursion takes O(n) space. A table of which slices read the same backwards removes the repeated checks.

Count the ways to place queens that cannot attack

Place one queen per row. Keep sets of used columns and used diagonals (row - col and row + col identify them). In each row, try only free columns, recurse to the next row, then remove the queen. O(n · n!) is a loose worst-case bound, and the search is far below it in practice because the sets prune early. The sets and the recursion take O(n) space.

Every distinct order when songs repeat

Sort the ids, then build orderings as usual with used flags, but skip a song when it equals the previous id and that previous copy is not in use. This makes equal copies always appear in the same relative order, so each distinct ordering is built once. O(n · n!) worst case, much less with many repeats. Apart from the output, it uses O(n) space.

The backtracking template: choose, explore, undo

Backtracking builds a solution one choice at a time. At each step it makes a choice, recurses to make the rest, then undoes the choice so the next option starts from a clean state. Record an answer when the path is complete; stop a branch the moment it cannot lead to one. The cost is the size of the decision tree, often exponential, so pruning matters.

Pruning: making exponential searches fast enough

Pruning cuts branches that cannot produce an answer. Common kinds: bound checks (the total already passes the goal), feasibility checks (not enough items left), ordering (sort so the first overshoot ends the loop), duplicate skipping (equal values at the same depth) and constraint sets (used columns and diagonals). The worst case stays exponential, but typical inputs shrink dramatically.

How big is the search space?

Count the leaves of the decision tree: two choices per item gives 2ⁿ, choosing an order gives n!, k choices per position over L positions gives kᴸ. Multiply by the work per leaf (often O(n) to copy). As a rough guide, 2²⁰ is about a million and 10! is about 3.6 million, so n around 20 for selections and around 10 for orderings is the practical limit.