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.

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.

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.

Canonical examples

Subsets

Every subset of [1, 2, 3] corresponds to a node in the recursion tree. The tree has depth 3 and 2^3 = 8 nodes total - one per subset, from the empty set at the root to [1, 2, 3] at the deepest leaf. Recording path[:] at entry to each call (before the loop) is what captures all 8 subsets.

Combination sum

Find all combinations of candidates that sum to a target, where each candidate can be reused. Sorting enables break pruning: as soon as a candidate exceeds the remaining target, all later candidates (which are at least as large) can also be skipped. This transforms an O(n) per-level scan into an early exit.

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.

Practice problems

• Subsets - Record at every node; the simplest pure backtracking problem.
• Subsets II - Same as Subsets but requires skipping duplicates at each recursion depth.
• Combination Sum - Reuse allowed; sort plus break pruning.
• Permutations - Used array; every element exactly once.
• Letter Combinations of a Phone Number - One choice per position; loop over a digit's letters at each depth.
• Word Search - DFS backtracking on a grid; mark visited in-place and restore on return.
• N-Queens - Constraint satisfaction; prune when a new queen attacks any existing queen.