Backtracking

What is backtracking?

Backtracking is a depth-first search technique that builds a candidate solution one choice at a time, and abandons (backtracks from) a partial candidate as soon as it determines the candidate cannot be extended to a valid complete solution. The three-step template: choose (add a candidate to the current path), explore (recurse), unchoose (remove it and try the next candidate). Every backtracking solution is this loop, applied recursively.

The property that makes backtracking efficient compared to brute force is pruning. If the current partial solution violates a constraint, return immediately without exploring any of its subtrees. Without pruning, backtracking is just enumeration. With tight pruning, it cuts the search space dramatically - an N-queens solver with constraint checks is orders of magnitude faster than generating all n! queen placements and filtering.

Two families of problems use backtracking. Generate-all problems produce every valid combination, permutation, or subset - the answer is all valid paths through the recursion tree. Constraint-satisfaction problems find one valid assignment or determine if one exists (N-queens, Sudoku). Both families use the identical choose-explore-unchoose template; the difference is whether you collect every leaf or stop at the first valid one.

Backtracking vs dynamic programming: backtracking generates all paths explicitly and pays the cost of each one. DP caches results to avoid recomputing overlapping subproblems. If the problem asks "how many?" and subproblems overlap, DP is faster. If it asks "list all valid arrangements" or "does any valid arrangement exist?", backtracking is the right tool.

Core operations

Key patterns

Subset generation

Build every subset by walking a start index forward, recording the path at each node along the way.

When to use - the task is to enumerate all subsets or the full power set, often under a constraint like a fixed size or no duplicates. The phrasing "all subsets", "every combination", or "the power set" is the tell. There are 2^n subsets, so this only works when n is small (around 20 or fewer); each path copy costs O(n), making the whole search O(n * 2^n).

How it works - follow the choose-explore-unchoose template: append nums[index], recurse, then pop it back off. Record path[:] at the top of every call, before the loop, because in subset generation every node of the recursion tree is a valid answer - from the empty set at the root to the full set at the leaves. The loop runs from start to the end and recurses with start + 1, which forbids re-selecting earlier elements and so visits each subset exactly once. To skip duplicates in a sorted array, this index-based form uses the rule i > start and nums[i] == nums[i-1] to avoid picking the same value twice at one level - do not confuse it with the used-array rule that permutations use.

Example: all subsets of [1, 2, 3]. The root call records {} before choosing anything, then appends 1 and recurses with start = 1; that branch records {1}, dives to {1, 2} and {1, 2, 3}, and pops its way back to try 2 and 3. Each pop hands the level back a clean path, so the remaining branches record {2}, {2, 3}, and {3} - eight snapshots in all, one per node. The visualizer below walks the tree node by node.

Combination sum (reuse allowed)

Like subset generation, but each candidate can be picked more than once on the way to a target sum.

When to use - the problem asks for all combinations that reach a target and lets you reuse a value (coin change that lists every way, combination sum). The signal is "all combinations summing to X" with repeats allowed. The search is still exponential in the worst case, so it relies on the input and target being small.

How it works - the only structural change from subsets is the recursive index: pass index, not index + 1, so the same candidate stays available on the next level and can be appended again. Sort the candidates first; then once candidates[index] > remaining, every later candidate is also too large, so you can break the loop instead of continue and drop the rest of that level entirely. Record a path only when remaining hits zero, since here a valid answer is a complete sum, not every node.

Example: combinations summing to 8, reuse allowed. Given sorted candidates [2, 3, 5], each pick recurses with the same index, so {2} re-appends 2 down to {2, 2, 2, 2} where remaining hits 0. Popping back to {2} and picking 3 opens {2, 3}, where reuse lets the same level pick 3 again for {2, 3, 3}; a later branch pairs 3 with 5 for {3, 5}. The sorted break prunes any candidate above remaining - the visualizer below marks those dead leaves.

Permutation generation

Build every ordering by trying each unused element at each position, tracked with a used array.

When to use - the problem asks for all arrangements where order matters and every element appears exactly once (permutations, anagram generation). The tell is "all orderings" or "all arrangements". There are n! permutations, so this is only feasible for small n; storing them all costs O(n * n!).

How it works - there is no start index here, since order matters and earlier elements can still be reused at later positions. The loop always begins at 0, and a used boolean array marks which elements are already in the current path so each appears once. Apply choose-explore-unchoose: mark used, append, recurse, then unmark and pop - and resetting used[index] = False on the way out is as critical as the pop, because siblings share that array. Collect a path when its length equals n. To skip duplicates in a sorted array, permutations use a used-array rule - skip nums[i] when nums[i] == nums[i-1] and nums[i-1] is not currently used - which is a different mechanism from the index-based i > start skip that subsets use.

Example: all orderings of [1, 2, 3]. The root loops from 0 and picks 1 first, marking used[0] = True and appending it; deeper levels pick 2 then 3, and the full path [1, 2, 3] is collected as permutation #1. Popping back, each level unmarks its element with used[index] = False so siblings can pick it - that reset is what lets the second leaf be [1, 3, 2], and the pattern repeats under 2 and 3 until all six orderings are collected. The visualizer below walks all six leaves.

When to reach for backtracking

• The problem asks you to generate all valid combinations, permutations, subsets, or paths - the answer is a list of lists.
• The problem involves placing elements under mutual constraints (N-queens, Sudoku) where each placement restricts future options.
• A brute-force nested loop is infeasible (exponential choices) but pruning can eliminate large branches early based on a constraint check.
• The problem says "find all ways to...", "enumerate all...", or "is there any valid assignment?" with dependencies between choices.
• You need to undo choices after exploring them - a grid word search that marks visited cells is backtracking even if it looks like plain DFS.
• The problem has a decision tree structure where each node is a choice and each leaf is a complete candidate - you need to explore the whole tree or stop at the first valid leaf.
• The input size is small enough (n <= 20 or so) that exponential time is acceptable, and the constraint-check is cheap.