Backtracking is systematic trial-and-error: build a candidate answer incrementally, recurse when it looks promising, and undo the last choicewhen you hit a dead end. The choose → explore → unchoose loop explores an entire decision tree while pruning subtrees that can't lead to valid solutions.
Backtracking is just DFS walking a tree of half-built answers: at every node you make a choice, recurse deeper, then undo that choice so the next branch starts from a clean slate. Choose → explore → un-choose — the undo is the whole trick.
Stop picturing loops. Picture a tree of decisions. The root is the empty answer. Each edge is one choice you could make next (“include this number”, “put a queen here”, “step onto this cell”). Each node is the partial candidate you've built so far. A leaf is a complete candidate— record it if it's valid.
Backtracking is nothing more than a depth-first traversalof that tree. You never build the tree in memory — it's implicit. The call stack is the path from the root to wherever you currently stand, and your mutable path array is the list of choices along that route.
Inside the recursive helper, the same three beats appear together, every time:
path.push(choice). You've just walked one edge down the tree.backtrack(...). This descends into the whole subtree of everything that choice makes possible.path.pop(). You step back up to the decision point so the next sibling branch starts from a clean path.That third beat is literally why it's called back-track: you retreat to the last fork and try the next road. Skip the un-choose and every branch inherits the previous branch's choices — the path only ever grows, and the answers go wild.
push has exactly one pop, with the recursion sandwiched between them. If you see a push with no matching pop, that's the bug.Watch the tree grow. Each level decides the next number; the ◄ marks where we record a candidate and ▲ marks the back-track (the un-choose that pops the last number off the path):
subsets([1,2,3]) — at each level decide: include the next number or not? start = [] ◄ record [] ├─ +1 → [1] ◄ record [1] │ ├─ +2 → [1,2] ◄ record [1,2] │ │ └─ +3 → [1,2,3] ◄ record [1,2,3] │ │ ▲ leaf — un-choose 3, back up │ └─ +3 → [1,3] ◄ record [1,3] │ ▲ un-choose 3, then un-choose 2, back up ├─ +2 → [2] ◄ record [2] │ └─ +3 → [2,3] ◄ record [2,3] └─ +3 → [3] ◄ record [3] 8 nodes = 2^3 subsets. ▲ = the back-track: pop the last choice, so the next sibling branch starts from a CLEAN path.
Now zoom into the one mutable patharray as a single descent and unwind play out. Notice it's the same array the whole time — push to go down, pop to come back up:
path starts [] ── the SAME array, mutated as we walk and un-walk ── push 1 → [1] (choose 1, recurse) push 2 → [1,2] (choose 2, recurse) push 3 → [1,2,3] (choose 3, recurse → leaf → record [...path]) pop 3 → [1,2] (UN-choose 3) ▲ back up one level pop 2 → [1] (UN-choose 2) ▲ back up one level push 3 → [1,3] (now try the sibling: choose 3 → record) pop 3 → [1] ... and so on. The pop is non-negotiable: skip it and [1] would still hold [2,3] when you try the [1,3] branch. Every push has its mirror pop.
When a problem says “find all…” or “enumerate every…”, don't reach for the template yet. Answer these four questions first — the structure of the recursion falls out of them:
start onward; for permutations it's every index not yet used.n”, “remaining sum is 0”, “all rows filled”, “reached the last cell”.Strip away the specific problem and every backtracking solution is the same six moves: base case → loop choices → prune → choose → explore → un-choose. Read it as a sentence, not as code:
backtrack(path, choices): # path = choices made so far (the route
# from the root to where I'm standing)
if path is a complete answer: # 1. BASE CASE — found a leaf worth keeping
record a COPY of path # results.push([...path]) ← copy, not the
return # live array!
for each choice in choices: # 2. branch into every option at this node
if choice is invalid: # 3. PRUNE — if this branch can't lead to a
continue # valid answer, skip the whole subtree
path.push(choice) # 4. CHOOSE — commit to this option
backtrack(path, rest) # 5. EXPLORE — recurse one level deeper
path.pop() # 6. UN-CHOOSE— undo, so the next sibling
# starts from a clean pathThe only things that change between problems are: what counts as a complete answer, what the choices at each node are, and what makes a branch invalid. The choose / explore / un-choose spine never changes — which is exactly why backtracking becomes second nature once this skeleton is in your hands.
Brute force generates every candidate, then throws away the invalid ones at the end. Backtracking does something smarter: it detects a dead branch at an internal node and skips the entire subtree below it in one check. One prune can erase thousands of leaves you never have to visit.
combinationSum([2,3], target = 7) — remaining = target so far [] r=7 ├─ +2 → [2] r=5 │ ├─ +2 → [2,2] r=3 │ │ ├─ +2 → [2,2,2] r=1 │ │ │ └─ +2 → r = -1 ✗ PRUNE (overshot) │ │ └─ +3 → [2,2,3] r=0 ✓ record! │ └─ +3 → [2,3] r=2 │ └─ +3 → r = -1 ✗ PRUNE └─ +3 → ... One check — "if (remaining < 0) return" — kills an ENTIRE subtree the moment a branch can't possibly reach 0. Brute force would walk every leaf; pruning lops off the dead limbs before you climb them.
Backtracking and brute force share the same worst-case bound — when nothing can be pruned, you still touch every leaf. But on real inputs, pruning early and often is the difference between instant and timing out. Put the prune as the first thing inside the loop (or the top of the call), before you choose, so you never pay for the recursion at all.
if (remaining < 0) return or if (col attacked) continue must run before path.push, or you waste a whole descent discovering what you could have known at the fork.Two invariants make or break a backtracker. Say them out loud before writing the helper, and the two classic bugs simply never happen:
results.push([...path]), never results.push(path). The path keeps mutating after the push, so storing the reference leaves you with a list of identical (usually empty) arrays — the aliasing bug. Snapshot at the moment of recording.path.pop() after the recursive call is mandatory. It restores the path to exactly what it was before this branch, so the next sibling explores from a clean state.Every backtracking solution has the same three-beat rhythm inside the recursive helper:
[...path]) and return.The undo step is what gives the technique its name — you back-track to the last decision point and try the next branch. Without it, every recursive call would share and corrupt the same mutable path.
path.push(x) · backtrack(...) · path.pop() — these three lines always appear together.Picture the recursion as a tree. Each node is a partial path; each edge is one choice. Leaf nodes are either complete solutions (record them) or dead ends (prune them). A depth-first traversal of this tree — which is exactly what the recursive helper performs — visits every node exactly once.
Pruning is what makes backtracking tractable. If you can determine at an internal node that no descendant can possibly be valid (e.g., the running sum already exceeds the target), you skip the entire subtree in one check. Good pruning transforms an impossibly large tree into a manageable one.
Backtracking is always exponential in the worst case. If the problem only needs the count or the optimum, reach for DP or math instead. Backtracking is justified when the problem literally asks you to enumerate all valid structures.
There are two canonical bookkeeping strategies:
start so the loop begins at start, not 0. This naturally avoids re-picking earlier elements and is perfect for combinations / subsets where order does not matter.Mixing them up is the single most common source of wrong answers — pick one based on whether your problem cares about ordering.
[1, 2, 3] by deciding each element in turn. Choose · explore · un-choose.Reach for backtracking whenever the problem asks you to enumerate every valid structure in a search space, and the space is too large to build explicitly but small enough (with pruning) to traverse.
| "generate all subsets / combinations / permutations" | backtrack with start-index or used[] |
| "find ALL solutions that satisfy constraints" | backtrack, push copy at base case |
| "partition a string / array all ways" | backtrack cutting at each valid split point |
| "place N items with constraints" (N-Queens, Sudoku) | backtrack row-by-row, prune by constraint sets |
| "explore a grid for a word / path" | grid DFS backtracking with visited marking |
| "combination sum / target with or without reuse" | start-index backtrack; reuse → pass i, no reuse → i+1 |
| "phone number letter combinations" / map-and-branch per character | backtrack branching on each mapped character set |
When → The universal starting point. Paste this, then fill in isComplete, isValid, and remaining for your specific problem.
function solve(input: unknown[]): unknown[][] {
const results: unknown[][] = [];
function backtrack(path: unknown[], choices: unknown[]): void {
// BASE CASE — a complete solution: record a COPY and return
if (isComplete(path)) {
results.push([...path]); // snapshot — never push the live ref
return;
}
for (let i = 0; i < choices.length; i++) {
const choice = choices[i];
// PRUNE — skip invalid branches early to cut search space
if (!isValid(path, choice)) continue;
// CHOOSE — extend the path
path.push(choice);
// EXPLORE — recurse deeper
backtrack(path, remaining(choices, i));
// UNCHOOSE — undo the choice (this is the "backtrack" step)
path.pop();
}
}
backtrack([], input);
return results;
}results.push([...path]), never results.push(path). The live array keeps mutating after the push; you'll end up with a list of identical empty arrays.When → The result is a set of elements where order doesn't matter. Pass a start index so later iterations never re-pick earlier elements. For combination sum with reuse, pass i instead of i + 1.
function subsets(nums: number[]): number[][] {
const results: number[][] = [];
function backtrack(start: number, path: number[]): void {
results.push([...path]); // every prefix is a valid subset
for (let i = start; i < nums.length; i++) {
path.push(nums[i]); // choose nums[i]
backtrack(i + 1, path); // only look at elements AFTER i
path.pop(); // unchoose
}
}
backtrack(0, []);
return results;
}
// Combination Sum variant: allow reuse by passing i (not i+1)
function combinationSum(candidates: number[], target: number): number[][] {
const results: number[][] = [];
function backtrack(start: number, path: number[], remaining: number): void {
if (remaining === 0) { results.push([...path]); return; }
if (remaining < 0) return; // prune: went over the target
for (let i = start; i < candidates.length; i++) {
path.push(candidates[i]);
backtrack(i, path, remaining - candidates[i]); // i, not i+1 → reuse allowed
path.pop();
}
}
backtrack(0, [], target);
return results;
}backtrack(i, ...) (allow the same index again) vs. backtrack(i + 1, ...) (each element used at most once).When → The result is an ordered arrangement — every position matters. A used[] boolean array tracks which indices are currently in the path so that any unused element can fill the next slot.
function permutations(nums: number[]): number[][] {
const results: number[][] = [];
const used = new Array(nums.length).fill(false);
function backtrack(path: number[]): void {
if (path.length === nums.length) {
results.push([...path]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue; // already in this path
used[i] = true;
path.push(nums[i]);
backtrack(path);
path.pop();
used[i] = false; // restore for sibling branches
}
}
backtrack([]);
return results;
}When → The input contains duplicate values and the output must have no duplicate results. Sort first, then skip any element that equals its predecessor at the same recursion level (i.e., when i > start and nums[i] === nums[i-1]).
// Deduplication pattern: sort + skip if same value as previous sibling
function subsetsWithDups(nums: number[]): number[][] {
nums.sort((a, b) => a - b); // sort first — groups duplicates together
const results: number[][] = [];
function backtrack(start: number, path: number[]): void {
results.push([...path]);
for (let i = start; i < nums.length; i++) {
// Skip a duplicate at this level of the tree (same sibling, not same path)
if (i > start && nums[i] === nums[i - 1]) continue;
path.push(nums[i]);
backtrack(i + 1, path);
path.pop();
}
}
backtrack(0, []);
return results;
}
// For permutations with duplicates, add: if (i > 0 && nums[i] === nums[i-1] && !used[i-1]) continue;
// Grid DFS backtracking (word search, etc.):
// board[r][c] = '#'; // mark visited
// backtrack(r+1, c); backtrack(r-1, c); ...
// board[r][c] = original; // unmarki > start (not i > 0). Using i > 0 would incorrectly skip a value the first time it appears at this level.results.push(path) stores a pointer to the same array you keep mutating. By the time backtracking finishes, every entry in results points to the same final (empty) array. Fix: results.push([...path]) at every base case.
Omitting path.pop() after the recursive call means the path only ever grows. Sibling branches inherit all previous choices, producing wildly wrong results. The choose and unchoose lines must always mirror each other — one push, one pop, with the recursion in between.
When the input has repeated values (e.g., [1,1,2]), the decision tree has multiple branches that produce the same subset or combination. Sort the input first, then guard with if (i > start && nums[i] === nums[i-1]) continue. The condition must use i > start, not i > 0.
Without a pruning check, the backtracker visits all exponentially many leaves. For combination-sum problems, add if (remaining < 0) return at the top of the function. For constraint-placement problems (N-Queens, Sudoku), check column and diagonal conflicts before recursing, not after. Pruning should be the first thing inside the loop.
board[r][c] = '#' before recursing and restore it after — the board itself serves as the visited set.#78SubsetsClassic powerset via start-index: every prefix of the path (including the empty one) is a valid subset — push a copy on every call, not just at a base case.#46Permutationsused[] array: at each level, loop all indices and skip used ones; push a copy when path.length === nums.length.#90Subsets IISort + skip duplicate siblings: same powerset skeleton as Subsets, but add the i > start && nums[i] === nums[i-1] guard to deduplicate.#40Combination Sum IISort + skip + i+1: each element used at most once (advance index), but skip a value that equals its predecessor at the same level to avoid duplicate combinations.#131Palindrome PartitioningAt each position, try every suffix prefix that is a palindrome; push it into the path and recurse on the remainder. Only copy the path when the entire string is consumed.#17Letter Combinations of a Phone NumberMap each digit to its letter set; backtrack through digits one at a time, branching once per letter. start-index is not needed — each level corresponds to one digit position.#51N-QueensPlace one queen per row; prune by tracking occupied cols, diag1 (r−c), and diag2 (r+c) in Sets. O(n!) worst case but heavy pruning makes it feasible for n ≤ 9.#140Word Break IIReturn every sentence formed by inserting spaces so each piece is a dictionary word. Backtrack from each index trying dictionary prefixes, and memoize start-index to all suffix sentences to avoid exponential recompute.#37Sudoku SolverFill a 9×9 Sudoku by backtracking: place a legal digit in the first empty cell (checked against row, column, and 3×3 box sets), recurse, and undo on failure. Used-sets make each legality test O(1).