Backtracking

Backtracking is systematic brute force: explore every choice, but the instant a partial choice can't possibly lead anywhere valid, abandon it and try the next one instead of continuing to build on top of it. Every problem in this topic is the same three-step template wearing different clothes — the differences are all in what "choice" means and what "can't possibly work" means.

The template: choose, explore, un-choose

Almost every function in this topic has the same shape: mutate some shared state to represent "I've made this choice," recurse to explore everything that follows from it, then undo that exact mutation before trying the next choice. That undo step is what makes backtracking different from plain recursion — you're reusing one mutable structure (a path vector, a "used" array, the grid itself) across the entire search tree instead of copying it at every level, and the undo is what keeps that safe.

void backtrack(/* position in the search */) {
    if (/* complete solution */) { record it; return; }
    for (each candidate choice at this point) {
        if (choice is obviously invalid) continue; // prune
        make the choice   // mutate shared state
        backtrack(next position)
        undo the choice    // <-- the line that's easy to forget
    }
}

Pruning is what separates backtracking from brute force

Generating every candidate and checking validity only at the end is still technically correct — it's just wasteful. The real skill in this topic is pushing the validity check as early as possible, so an entire doomed subtree gets skipped instead of explored. Combinations prunes when too few elements remain to ever reach length k. Combination Sum prunes (using sorted order) the instant a candidate would overshoot the target. Palindrome Partitioning prunes the instant a candidate piece isn't a palindrome, rather than building a complete partition and checking every piece afterward — for a string with no repeated characters, that difference is the gap between exploring one path and exploring billions.

The duplicate-handling pattern

Subsets II and Permutations II both solve the same meta-problem: the input has duplicate values, and naively running Subsets or Permutations unmodified produces duplicate outputs. The fix in both cases is sort first, then skip a duplicate candidate at the same decision point — but "same decision point" means something subtly different in each: for subsets, it's "the same recursion level" (i > start); for permutations, it's "this identical value's earlier copy is still unused" (!used[i-1]). Getting the exact skip condition right — not just "skip if it equals the previous element," full stop — is what actually distinguishes these from their non-duplicate-safe cousins.

Constraint tracking instead of full re-validation

N-Queens II could check every new queen against every previously placed queen on each attempt — that works, but rescans state that a placement earlier already resolved. Tracking three boolean arrays (occupied columns, and both diagonal directions) turns "is this placement legal" from a scan into a lookup — the same shift from "recompute" to "maintain incrementally" that shows up constantly once you're looking for it.

Common mistakes

• Forgetting the undo step — mutating a path, a used-array, or a grid cell without restoring it before the next iteration corrupts every sibling branch that runs afterward.
• Checking validity only at the leaf instead of pruning mid-construction — technically correct, but throws away most of the benefit backtracking has over pure brute force.
• Deduplicating wrong — skipping "any index with a value seen before" (globally) instead of "the same value at this specific decision point" silently drops valid results, not just duplicate ones.
• Allowing reuse when the problem forbids it (or vice versa) — the only difference between Combination Sum (reuse allowed) and Combination Sum II (reuse forbidden) is recursing to the same index versus the next one; mixing these up is an easy, quiet mistake.