Backtracking: choose, explore, un-choose

When you need it#

Most problems so far asked for a number: the largest sum, the shortest path, how many. Backtracking is for the ones that ask for the arrangements themselves: every subset, every permutation, every way of placing the queens, every path through the maze.

The giveaway is a question that begins "list all" or "find a valid", where the answer is built one decision at a time and a decision can turn out to be wrong.

The shape#

walk(state):
    if the state is an answer:
        record it

    for each choice available here:
        apply the choice          # choose
        walk(the new state)       # explore
        undo the choice           # un-choose

Three lines in the loop, and the names are worth learning as a phrase: choose, explore, un-choose. Every backtracking solution has this shape. What changes between problems is only what a choice is, and what makes a state an answer.

The line everybody forgets#

The undo.

It is needed because the state is one object shared by every branch. When the walk comes back up from a branch, the state must look exactly as it did going in, or the next branch starts from somewhere it was never meant to be.

Leaving it out produces answers that are too long, or repeated, or simply wrong, and the code still looks reasonable. If a backtracking solution is misbehaving, this is the first thing to check.

The alternative is to pass a copy at each step, which needs no undo and costs a copy per node. For small states that is often the clearer trade.

The cost is the answer count#

Every subset of n numbers means two choices per number, so two to the power of n answers. Every permutation means n factorial. Those are enormous, and no technique makes them smaller, because the answers really are that many. Backtracking is not slow: the question is big.

This is why the limits on these problems are small. Seeing n <= 15 in the constraints is itself a hint that an exponential walk is expected.

Pruning is where the skill is#

What backtracking lets you do is stop early. If a partial state already breaks the rules, there is no point exploring anything below it, and cutting it off removes that entire subtree.

Placing queens, you check the new queen against the ones already placed before recursing. Solving a maze, you stop at a wall. Word search, you stop the moment the letters stop matching a real word.

The walk is the easy part. Deciding what can be ruled out early is the part worth thinking about, and it is usually the difference between a solution that finishes and one that does not.

Getting one right#

1. Say what a choice is.
2. Say what makes a state an answer.
3. Say what makes a state hopeless, so you can stop early.
4. Then write the three lines.

Practice in order#

1. Every subset, the pattern at its smallest, where the undo is easiest to see.
2. Generate parentheses, where the conditions on each choice mean nothing invalid is ever built, so nothing has to be checked at the end.
3. Combination sum, which differs from subsets by one character: recursing on i instead of i + 1 is what lets a number be reused.
4. Permutations of a word, where stopping duplicates being made is one line and getting that line right takes a minute of thought.
5. N queens, where pruning is not an optimisation: without it nothing finishes.
6. Word search, the same walk on a grid.