Backtracking: The Core Idea

Backtracking is the pattern for "find all": all subsets, all orderings, all combinations that hit a target, all valid boards. The question does not want the best answer. It wants every answer, or it wants to know whether any answer exists at all.

Think of a combination padlock with three wheels. You set the first wheel, then the second, then the third, and test. If the lock stays shut, you do not start again from nothing. You turn back only the last wheel and try its next digit. When the last wheel has tried every digit, you step back one more wheel. That "step back one decision and try the next option" is the whole pattern.

How to recognise it

Signal 1 — the words "all", "every", "list each". "Return all subsets." "Print every valid way to place the queens." If the output is a list of lists, or a list of strings you must build, you are probably here.

Signal 2 — building something under rules. N-Queens, Sudoku, a word traced through a grid. There is a partial answer, a set of legal next moves, and a rule that says when the answer is finished.

Signal 3 — a very small n. This is the signal most candidates miss. Read the constraints before the story:

A problem that caps n at 12 is telling you exponential work is expected. Nobody writes that limit by accident. If you hunt for a polynomial solution to a problem whose output is exponential, you waste ten minutes and find nothing.

What backtracking is not. Every other pattern in this course turns a slow approach into a fast one. Backtracking does not. There are 2ⁿ subsets of n items, and printing them takes at least 2ⁿ steps however clever you are. What backtracking buys is not exploring branches that cannot lead to an answer. For plain subsets there is nothing to cut, so it is pure listing. For N-Queens, cutting is the difference between 16.8 million boards and about two thousand.

How it works: the decision tree

Take the subsets of [1, 2, 3]. Start with nothing chosen: the empty subset, which is itself an answer. From there, you may add any element that comes after the last one you took. That "only look forward" rule is what stops [1, 2] and [2, 1] both appearing.

                        []                      start = 0             ┌──────────┼──────────┐           [1]         [2]        [3]           start = 1, 2, 3        ┌────┴───┐      │     [1,2]     [1,3]  [2,3]                     start = 2, 3, 3       │    [1,2,3]                                     start = 3

Eight nodes, eight subsets. For subsets, every node is an answer. For permutations only the leaves are, because an ordering is not finished until every element is placed.

The key thing to see is that there is one working list, changed in place as the walk goes down and back up:

Every "choose" has exactly one matching "undo". The tree never exists in memory. Only the path from the root to the current node exists — that is the recursion stack, at most n deep. The tree is the shape of the work over time.

Why it is correct: the invariant

The whole pattern rests on one promise: when a recursive call returns, the working state is exactly what it was before the call. Call it the "leave no trace" rule.

If every call keeps that promise, each branch starts from a clean state that holds only the choices on its own path. Branch [2] never sees the 1 that branch [1] added, because branch [1] removed it on the way out. Break the promise once — forget one pop() — and every later branch inherits stale choices. The output still looks like a list of lists, which is why this bug survives a quick glance.

The second promise is about recording. The working list keeps changing, so when you record an answer you must record a copy. Store the live list and every stored "answer" is the same object, which ends the walk empty.

The shapes it takes

Almost every backtracking problem is one of four shapes. They share the template and differ in three places: where the loop starts, what the recursive call passes, and when you record.

The recursive call's argument carries the meaning. Passing i + 1 says "move past this element". Passing i says "this element may be used again". Passing nothing and using a used array says "any element I have not placed yet". One token, three different problems.

The template

1def backtrack(state: list, start: int) -> None:2    if is_complete(state):3        results.append(state[:])        # record a COPY, never the live list4        return                          # (for subsets: record, but don't return)5    for i in range(start, len(choices)):6        if not is_valid(choices[i], state):7            continue                    # prune: this branch cannot succeed8        state.append(choices[i])        # 1. choose9        backtrack(state, i + 1)         # 2. explore10        state.pop()                     # 3. undo

Read it line by line:

• is_complete — the finish rule. For subsets, every node counts. For permutations, the path has n elements. For N-Queens, every row has a queen.
• results.append(state[:]) — the copy. state[:] costs O(length of the path), and that cost is why subsets take O(n × 2ⁿ) and not O(2ⁿ).
• the for loop — the legal choices at this node. A start index, a used array, or a fixed list of options decides what they are.
• if not is_valid(...) — the pruning test. It sits before the recursive call so a doomed branch is never entered.
• choose / explore / undo — three lines that always travel together. Write the undo line at the same moment you write the choose line, before you write the call between them.

There is a second style that passes a new list down, backtrack(path + [x], i + 1), and needs no undo. It is shorter and cannot forget a pop(), but it allocates a fresh list at every node. Use the mutate-and-undo form as your default: it is what interviewers expect, and it scales when the state is a board or three sets rather than one short list.

Pruning: the only speed-up there is

At every node ask: can this partial answer still lead to a valid one? If not, stop now. Every node you skip removes its whole subtree, so a cut near the root is worth far more than a cut near a leaf.

N-Queens shows the size of the win. With one queen per row on an 8 × 8 board, trying every column in every row means 8⁸ = 16,777,216 full boards. Checking each square against the queens already placed, and refusing attacked squares at once, the search makes 2,057 recursive calls in total to find all 92 solutions. That is about eight thousand times less work, from one continue.

Where to put the test matters. In Palindrome Partitioning (split a string so every piece is a palindrome), you can check each piece before recursing, or check the whole split at the end. Both give the same answer. The first never enters a split whose first piece is already wrong; the second walks every one of the 2ⁿ⁻¹ ways to split and rejects most at the bottom.

When pruning is not enough, order the choices. In Sudoku, fill the empty cell with the fewest legal digits first. Fewer branches near the root means a much smaller tree. It is a heuristic, not a guarantee, and worth saying out loud even if you do not code it.

Complexity

Time = number of nodes in the tree × work per node. Where you cannot prune, the node count is the size of the answer space:

For constrained problems such as N-Queens there is no neat formula for the pruned tree. Be honest: give the unpruned bound (O(n!) for N-Queens, since each row takes a column not yet used) and say that pruning cuts it hard.

Space has two parts, and interviewers want them apart. The working space is the recursion stack plus the path: O(depth), usually O(n). The output space is whatever you return: O(n × 2ⁿ) for subsets. "O(n) extra, plus the output" is the precise answer.

Where it goes wrong

Four bugs cause almost every wrong backtracking answer, and none of them crashes.

1. Recording the live list. results.append(path) stores a reference. At the end every entry is the same list, usually empty. Fix: path[:] or list(path).
2. A missing undo. Every change on the way down needs an undo on the way up, and there can be several. N-Queens changes four things per choice — a list and three sets — so it needs four undo lines. Miss one and later branches are rejected for clashing with a queen that is no longer on the board.
3. The wrong recursive argument. Passing i where you meant i + 1 reuses elements, and if nothing shrinks each call, it recurses forever. Passing 0 where you meant i + 1 produces every ordering of every subset — far too many answers.
4. No pruning. Correct on the sample, too slow on the real input. When that happens, the fix is never "make each node faster". It is "which test before the recursive call kills a subtree?"