Backtracking
AlgorithmsHigh priority~1.5 hDFS over the decision tree — build a candidate one choice at a time, and undo the moment it can't work.
Definition
Backtracking builds a solution incrementally, one choice at a time, and backtracks — undoes the last choice — the moment a partial candidate can't possibly lead to a valid one. It's a depth-first search over an implicit tree of decisions: each node is a partial candidate, each edge is one choice, and each leaf is either a complete answer or a dead end.
The shape is always the same three moves: choose (extend the candidate with one option), explore (recurse on the extended candidate), unchoose (undo the choice before trying the next option, so sibling branches start from clean state). Because every option at every depth is tried, the raw search tree is exponential — the whole game is pruning branches early, the moment a partial candidate provably can't be completed, so the search never wastes time finishing a doomed path.
When to use
Reach for backtracking when a prompt asks for all ways to do something — all permutations, all subsets, all combinations reaching a target, all valid boards — under some constraint, and there's no greedy or DP shortcut because you genuinely need to enumerate. Tell-tales: "return all…", "generate every…", "find all valid arrangements", or a constraint-satisfaction puzzle (N-Queens, Sudoku, word search) where a placement can be checked incrementally.
It's the wrong tool when the prompt wants a single optimal count or value and the subproblems overlap — that's dynamic programming territory (backtracking without memoization re-explores the same partial state many times; add memoization and you've turned it into top-down DP).
Techniques
Choose–explore–unchoose — the base template every variant below specializes: push a choice onto the path, recurse, pop it back off. Getting the unchoose step right (restoring shared state exactly) is the one line that separates a working backtracker from a silently corrupted one.
Include/exclude (subset generation) — at each element, branch two ways: take it or skip it. n binary decisions build all 2ⁿ subsets (subsets).
Used-flag or swap-based permutation generation — at each position, try every element not yet placed (a used array), or swap candidates into place and swap back. n positions with shrinking choices build all n! orderings (permutations).
Combination with reuse and pruning — walk candidates from a fixed start index so combinations never repeat as a reordering; sort first so a running sum that exceeds the target lets you break out of the whole remaining loop instead of trying every larger candidate (combination sum).
Constraint-satisfaction placement — place one piece per row/position and track why a cell is unsafe in O(1)-lookup sets (columns, diagonals) so each placement is checked without rescanning the board (N-Queens, Sudoku).
Character-by-character construction — build a string one position at a time from a small alphabet per position, the same include/exclude shape specialized to strings (letter combinations of a phone number). Steering the same recursion with a trie prunes whole prefixes at once when the candidates are drawn from a fixed dictionary (word search II).
Related concepts
Backtracking is depth-first search — the decision tree is an implicit graph, and "unchoose" is just the graph DFS's implicit unwind made explicit because the "visited" state here is a mutable path, not a fixed set of nodes. Add a memo table keyed by the partial state and the exact same recursion becomes top-down dynamic programming — backtracking explores a tree, DP collapses it into a DAG by reusing identical subproblems. A trie often steers a backtracking search over strings, pruning every branch that shares a dead prefix at once instead of one candidate at a time.
Implementation
function backtrack(path, state) {
if (isComplete(path, state)) {
record(path); // save a copy — never the live, still-mutating array
return; // (or `return true` if only one answer is needed)
}
for (const choice of choicesFrom(state)) {
if (!isSafe(choice, path, state)) continue; // prune — skip doomed branches early
apply(choice, path, state); // choose
backtrack(path, state); // explore
undo(choice, path, state); // unchoose — restore state for the next option
}
}Worked examples
Generate every subset — the cleanest illustration of choose–explore–unchoose: at each element there are exactly two choices, include it or skip it, so the search is a perfect binary decision tree of depth n. Take [10, 20, 30]. Depth-first, the search tries include at every level first, records the full subset at the bottom, then unwinds one level at a time to try skip at each level in turn.
nums = [10, 20, 30] — decision tree of include/skip choices
Start at index 0 with an empty path. Try the *include* branch first: choose 10.
One level deeper. `marked` here means "already chosen", not "discarded" — 10 is locked into the path.
All three included — a leaf. Record a *copy* of the path: [10, 20, 30].
Backtrack: pop 30 back off, then take the *skip* branch at the same depth. That's also a complete subset — record [10, 20].
Unwind one more level, pop 20, and take *skip* at index 1. The subtree under "20 excluded" still needs exploring for 30.
Finally pop 10 and take *skip* at the root. The mirrored right subtree (10 excluded) produces the remaining subsets the same way — after the full traversal, all 2³ = 8 subsets have been recorded.
function subsets(nums) {
const result = [];
const path = [];
const backtrack = (i) => {
if (i === nums.length) {
result.push([...path]); // copy — path keeps mutating after this
return;
}
path.push(nums[i]); // choose: include nums[i]
backtrack(i + 1);
path.pop(); // unchoose
backtrack(i + 1); // choose: skip nums[i] (no push at all)
};
backtrack(0);
return result;
}Every one of the 2ⁿ root-to-leaf paths is visited once, and each leaf costs O(n) to copy into the result, so the whole search is O(n · 2ⁿ) time and O(n) extra recursion depth beyond the output.
Things to look out for
- Forgetting to unchoose. Skip the
pop()/ flag-reset after the recursive call and state leaks into sibling branches — later paths get built on stale data from a branch that already finished. - Recording a reference instead of a copy.
result.push(path)stores the live array; once backtracking mutates it further, every recorded answer silently points at the same final (usually empty) array. Alwaysresult.push([...path]). - No pruning at all. A correct-but-unpruned search still visits every node of the full tree — check
isSafe(running sum vs. target, column/diagonal conflicts) before recursing, not after, or the search does the doomed work anyway. - Missing the duplicate-skip rule. When input has repeats but the output must not (
combination sum II-style), sort first and skip a candidate equal to the previous one at the same recursion depth — skipping unconditionally also throws away valid reuses at a deeper level.
Corner cases
- Empty input (
n = 0) — subsets should still return[[]](one empty subset); permutations of[]return[[]]too, not[]. - A single element — the smallest real branch: exactly one leaf for permutations, two for subsets (include/skip).
- No valid combination reaches the target — return
[], notnullor a thrown error. - A target of exactly 0 in a sum-based problem — decide up front whether the empty combination counts as a valid answer.
- A puzzle with zero solutions (N-Queens at
n = 2orn = 3) — the search must terminate having tried every branch and pruned all of them, returning an empty result rather than hanging.