Backtracking: Brute Force That Cleans Up After Itself

Backtracking is brute force with manners. It still tries every possibility, but instead of building each candidate from scratch it walks one decision tree, making a choice at every node and — the part that defines it — undoing that choice before it tries the next one. The same partial solution gets extended, abandoned, and reused thousands of times, which is only possible because every step that reaches forward is matched by a step that reaches back.

That symmetry is the whole template. Choose, recurse, un-choose:

void backtrack(State state, List<Result> results) {
    if (isComplete(state)) { results.add(snapshot(state)); return; }
    for (Choice c : choicesFrom(state)) {
        if (!allowed(c, state)) continue;   // prune: skip a doomed branch
        apply(c, state);                    // choose
        backtrack(state, results);          // explore everything downstream
        undo(c, state);                     // un-choose — restore state for the next choice
    }
}

Every problem in this category is that skeleton with three blanks filled in: what a choice is, when a branch is doomed, and when a partial answer is complete. Miss the undo line and your state leaks from one branch into the next — it’s the bug I still reach for first when a backtracking solution returns garbage.

What the choice is

The shape of choicesFrom is what separates the problems:

• Include or exclude each element builds subsets. Subsets is the bare tree — at every element, branch two ways — and Combination Sum is the same with a running target you subtract into, reusing a number by simply not advancing past it.
• Pick an unused element builds permutations. The state carries a “used” marker so each element appears once per arrangement.
• Pick one option per position builds a Cartesian product. Letter Combinations of a Phone Number maps each digit to its letters and branches once at each position, so the tree is as deep as the input is long and as wide as the options at each step.
• Extend along a grid turns into Word Search, a graph DFS where “un-choose” means unmarking the cell you visited so other paths can use it.
• Satisfy a constraint is N-Queens, Palindrome Partitioning, and Generate Parentheses — place a queen only where none attack it, cut a string only where the prefix is a palindrome, add a ) only while the string can still be balanced.

Pruning is what keeps it from being hopeless

Backtracking’s worst case is genuinely exponential — $2^n$ subsets, $n!$ permutations — so when a problem’s constraints leave dead branches to cut, doing so early is often what stands between a solution that finishes and one that times out. (Pure enumeration like Subsets or Permutations has no infeasible branches to prune; its cost is the exponential output itself.) N-Queens never places a queen in a column or diagonal already under attack, so entire subtrees never get explored; Combination Sum stops the moment its running sum passes the target. A good allowed check is not an optimization you add later — it’s often the difference between a solution that finishes and one that doesn’t, because it prunes the branch before the recursion pays for it. And when the tree keeps reaching the same partial state down different branches, caching that state’s result is the exact step that turns a backtracking search into dynamic programming.

The duplicate trap

Subsets II and Combination Sum II add a wrinkle that catches people: the input has repeats, and you must not emit the same combination twice. The fix is a small ritual — sort the input first, then within a single level of the tree, skip a value identical to the one you just tried. Sorting brings equal values next to each other, and the skip rule stops you from starting two branches that would grow into identical results:

Arrays.sort(nums);
for (int i = start; i < nums.length; i++) {
    if (i > start && nums[i] == nums[i - 1]) continue;   // skip a duplicate sibling
    // choose nums[i]; recurse with start = i + 1; un-choose
}

The i > start is the whole subtlety. You skip a repeated value only when it’s a sibling at the same level of the tree — not when it’s the choice you just made one level up — because a legitimately repeated element still needs to appear once along a path. Get that guard wrong and you either emit duplicates or drop valid answers; it’s the single most common place these problems break.

Where the tree gets too big to walk

The reason “catastrophic backtracking” is a phrase security engineers know is that a regular-expression engine backtracks exactly like this — it tries a match, fails, undoes, and tries another split of the string. Feed one a pathological pattern like (a+)+$ against a long non-matching input and the decision tree explodes into exponential retries; that’s a ReDoS vulnerability, a denial of service built entirely out of missing pruning. Constraint solvers and Sudoku engines are the same search wearing a friendlier face. Once you’ve watched a regex pin a CPU at 100%, the allowed check in N-Queens stops looking optional.

Fill in three blanks

The template never changes, so a backtracking problem is three decisions: what’s a choice, when do I prune, when am I done. Get the undo reflex into your fingers, sort-and-skip for duplicates, and prune before you recurse — and the ten problems are the same tree walked with different rules about where its branches are allowed to go.

References

• NeetCode 150 — Backtracking — the ten problems, all one template.