Backtracking search

Start with an enumeration a loop can handle: choose 2 numbers out of 5. Two nested for loops do it. Now change the problem to choose k out of n, where k is only known when the program runs. You cannot write "k nested loops", because the number of loop levels is fixed when you write the code. The same difficulty appears in "cut a string into any number of pieces" and "place queens until the board is full". These problems share one property: how many choices you make, and which choices are legal at each step, are decided while the search runs.

Here is the method, before it gets a name. You keep one partial answer. At each step you list the choices that are still allowed, take one, add it to the partial answer, and continue from there. When the partial answer is complete you record it. When it cannot be completed, or after you have recorded it, you remove the last choice you added and try the next choice at that same step. When a step runs out of choices, you return to the step before it and do the same thing there.

Draw every partial answer as a node and every choice as an edge, and you get a tree. This method is a depth-first search over that tree of partial answers, and the step that removes the last choice is called backtracking. That undo step is the whole difference between backtracking and ordinary recursion: it restores the shared partial answer to exactly what it was before this node was entered, so the next branch starts from a clean state. The tree is usually called a decision tree. It is never built in memory — it exists only as the shape of the recursion.

One step forward and one step back — that is the entire template: choose → recurse → un-choose. Every remaining problem in this chapter differs only in two things: what the decision tree looks like, and which branches can be cut before you enter them.

Backtracking problems look very different from each other, but they share one skeleton. Before writing code, answer three questions:

With those three answers, fill in the skeleton below. The example is "choose k numbers out of 1..n". Look at the three lines inside the loop — choose, recurse, un-choose — and note that the un-choose is the exact reverse of the choose.

Problem: given integers n and k, return every combination of k numbers from 1..n. Order does not matter, so [1,2] and [2,1] are the same combination. Brute force: if k were a constant you could write k nested loops, but k is a parameter. Solution: build a decision tree. Level 1 picks the first number, level 2 picks the second number from those larger than the first, and so on. Every node whose path has length k is one combination.

Here is the first key point of the combination family: why can the next level only pick a larger number? Because a combination is a set, not a sequence. If every level could pick any number, the search would produce both [1,2] and [2,1] — the same set twice. A startIndex that only moves forward forces every combination to appear exactly once, in increasing order. First, the full tree with no pruning (n=4, k=2):

Count the green leaves: exactly 6 = C(4,2). Now look at the branch that starts by picking 4. You still need 2 numbers in total, but you started at the last one, so no larger number is left and that branch can never produce a complete answer. The search entered it anyway and only found out at the bottom. This is what pruning fixes: before entering a subtree, check whether it can still lead to a valid answer, and skip it if it cannot.

For LC 77: you still need k − path.size() more numbers, so the starting value i can be at most n − (k − path.size()) + 1; beyond that there are not enough numbers left. Tighten the upper bound of the loop from n to that value and the dead branch is never entered at all:

Almost every combination problem adds a condition to the LC 77 skeleton. Once you see which single part changes, you stop mixing them up:

Cutting a string into pieces does not look like choosing numbers, but it is the same tree. One sentence is enough: read startIndex as "the first character of the next piece". At each node you try every cut point i from start to the end of the string; the substring s[start..i] is the piece you choose at this step. Reaching the end of the string means the whole string has been cut, which is one complete answer.

Problem: return all subsets of an array whose elements are distinct, including the empty set and the array itself. Key idea: for combinations a node counts only when the path has length k. For subsets the path itself is already an answer — the empty set, {1}, {1,2}, all of them. So subsets and combinations share the same startIndex tree, and differ in one thing only: when you record.

Combinations record at the leaves. Subsets record at every node, on entry, before the loop starts, because the path that leads to any node is itself a valid subset. In the animation every node turns green as it is recorded:

Problem: return all permutations of an array whose elements are distinct. The difference from combinations: order matters, so [1,2] and [2,1] are two different answers. That makes the "only move forward" startIndex wrong here: in [2,1] the 1 comes after the 2, so a forward-only search can never build it, and most of the answers go missing.

A permutation needs every level to reach every element that is not already on the path, including smaller ones. How do you know which ones are on the path? Keep a boolean array called used: used[i] = true means element i is currently on the path, and this level skips it. Watch used light up on a choose and go dark on an un-choose:

Notice that the un-choose restores two pieces of state, used and path. That is the extra trap permutations add on top of combinations. The loop starts from i = 0 at every level, never from a start index, and used does the filtering:

The problems so far (77 / 78 / 46) all assumed distinct elements. As soon as a value repeats — for example [1,1,2] — duplicate answers appear. Look at the symptom first: all subsets of [1,1,2], with no special handling:

{1} appears twice and so does {1,2}. The cause, in one sentence: inside the same loop, the second 1 opened a branch identical to the one the first 1 already opened. The fix is to sort first, so equal values sit next to each other, and then, inside the loop, skip a value that equals the previous one. With that rule the duplicate branch is never entered:

For combinations and subsets, which have a startIndex, the rule is written i > start && nums[i] == nums[i-1]. Note that it is i > start, not i > 0:

Here is why it is correct. After sorting, equal values are adjacent. At one node the loop tries index start, start+1, … as the next element of the path. Two indexes holding the same value leave the same remaining choices below them, so they generate identical subtrees: every answer found under the second one was already found under the first. i > start keeps the first index of each run of equal values at this node and skips the rest, so each distinct value is tried once per node.

And here is why it does not remove valid answers. The condition only compares an index with its sibling in the same loop. i == start is the first choice at this node and always passes. A deeper call receives start = i + 1, so a value equal to the one just taken arrives at the deeper node at position start and passes the test there. That is exactly why {1,1} survives while a second {1} branch does not. Writing i > 0 instead would also compare across levels and would delete {1,1}.

Permutations (LC 47) have no startIndex, so the rule is written i > 0 && nums[i] == nums[i-1] && !used[i-1]. The value of used[i-1] tells you which of the two situations you are in:

Problem: place n queens on an n×n board so that no two share a row, a column, or a diagonal, and return every arrangement. Building the tree: a valid board has exactly one queen per row, otherwise two would share a row. So the row number is the level of the tree and the column is the choice at that level. dfs(row) tries every column in row row; if the square is safe it recurses into row+1; reaching row n means all rows are filled and one solution is complete.

The work is in the safety check: before placing at (row, col) you must know that no queen above attacks it — same column, same "\" diagonal, or same "/" diagonal. Place a 4×4 board yourself below; watch the red conflicts and the dead end that forces a step back:

Those moments where a whole row has no safe square, so the queen in the row above has to move, are backtracking on a board. The safety check can be made O(1) with three sets that record which columns and which diagonals already hold a queen. Why do row − col and row + col identify a diagonal? Along a "\" diagonal, moving one square down-right adds 1 to both row and col, so row − col stays the same. Along a "/" diagonal, moving one square down-left adds 1 to row and subtracts 1 from col, so row + col stays the same. Each value therefore names exactly one diagonal.

Sudoku (LC 37) is the two-dimensional version of the same idea: find an empty cell, try the digits 1 to 9, place a digit that breaks no rule and recurse on the rest of the board, and erase it if the recursion fails. The row, column, and 3×3 box checks are its constraint pruning. A faster version packs the digits already used in each row, column, and box into the bits of one integer, which turns both the check and the "which digits are still allowed" question into bit operations. See chapter 04 · bit manipulation for representing a set with one integer and using lowbit to read candidates.