Introduction to Backtracking Pattern

You are given candidate numbers and a target. Find every combination that adds up to the target, where each candidate may be used any number of times.

candidates [2, 3, 6, 7]   target 7   gives [2, 2, 3] and [7]

The Subsets pattern would build every possible combination and then throw away the ones that miss the target. That is correct and wasteful. Once a partial combination has reached 8, no amount of adding will bring it back to 7, and yet the Subsets approach keeps extending it.

Backtracking is the same exploration with one addition: stop as soon as the partial answer cannot succeed.

Once the running total passes 7, that branch is abandoned. Everything below it, which could be thousands of combinations, is never built. The saving is not a constant factor. It removes whole regions of the search.

The other half of the pattern is what happens when a branch ends. You made a choice to get here, and you have to undo it before trying the next one. That undo is what gives the pattern its name.

Core idea

The Backtracking pattern explores choices one at a time, and abandons a branch as soon as it cannot lead to a valid answer. Each choice is undone on the way back.

Three things define any backtracking solution: what a choice is, when a partial answer is complete, and when a branch is hopeless.

How it works

1. Keep a partial answer, which starts empty.
2. If the partial answer is complete, record a copy of it and return.
3. If it can no longer succeed, return immediately without exploring further.
4. Otherwise, for each available choice: add it, recurse, then remove it again.
5. The removal in step 4 is what restores the state for the next choice.

The cost depends entirely on how much the pruning removes, so a single formula does not describe it. The worst case is still exponential, and the pruning is what makes real inputs finish.

Step 4 must record a copy when the answer is complete. Storing the partial answer itself means every stored result changes as the search continues.

Recognize it when

Use Backtracking when the question shows these signs.

• You need every valid answer, or one valid answer, out of many possible arrangements.
• Each step is a choice, and choices combine into a candidate answer.
• Some partial answers can be ruled out early, before they are finished.
• The wording says all combinations, all placements, or solve the puzzle.
• Generating everything and filtering afterwards would be far too slow.

It is not this pattern when:

• Every arrangement is valid, so there is nothing to prune. That is the Subsets pattern, and its loop is simpler.
• You need only the best answer and states repeat. That is Dynamic Programming, which remembers answers instead of re-exploring.
• A single sort settles the choice safely. That is Greedy.

The template

function search(partial, remainingChoices):
    if partial is a complete answer:
        record a copy of partial
        return

    if partial can no longer succeed:
        return                                  # prune this whole branch

    for each choice in remainingChoices:
        partial.add(choice)                     # make the choice
        search(partial, choices after this one)
        partial.removeLast()                    # undo it

The three lines that change between problems are the completeness test, the pruning test, and what counts as a choice. The add, recurse, remove rhythm never changes.

The pruning test is where the work goes. A weak test still gives correct answers and runs slowly. A wrong test is worse, because it removes branches that contained real answers.

Variants in this chapter

Word Search is worth extra attention. The undo step there is marking a cell as used and then unmarking it. That is easy to forget, and it produces answers that are silently too few.

Watch out for

• Forgetting to undo the choice. Without the removal, the partial answer keeps everything from every branch and the results are nonsense.
• Storing the partial answer instead of a copy. Every recorded result would then change as the search continues, and they all end up identical.
• Pruning too aggressively. A test that is not strictly true removes branches containing real answers. Losing answers is worse than being slow.
• Undoing in the wrong place. The undo belongs immediately after the recursive call, not at the end of the loop, and not inside a condition.
• Marking a grid cell without unmarking it. In grid searches the visited mark is a choice like any other, so it needs the same undo.

How this compares with nearby patterns

Backtracking and Dynamic Programming both explore a space of choices, and they differ in what they do about repetition. Backtracking re-explores and prunes. Dynamic Programming remembers a result and never computes it twice. When the same state can be reached by many routes, remembering wins.

Key Takeaways

• Backtracking is exploration plus pruning plus undoing.
• The pruning test is what makes it finish, and it must be strictly true.
• Record a copy when an answer is complete, never the partial answer itself.
• The undo belongs immediately after the recursive call.
• If nothing can be pruned, use the Subsets pattern instead.

Let's apply it to the first problem, Combination Sum.