Backtracking Patterns — Complete Guide

Backtracking is a systematic trial-and-error algorithm: you build solution candidates incrementally and abandon (backtrack) a partial candidate as soon as you determine it cannot possibly lead to a valid complete solution. This aggressive pruning is what makes backtracking efficient — rather than generating all possible sequences and filtering, you cut off entire subtrees of the search space the moment a constraint is violated.

The mental model that unlocks every backtracking problem is the decision tree. Each node in the tree represents a partial solution (a path you have built so far). Each edge represents a choice you make (an element you add to the path). Backtracking is simply depth-first search on this implicit decision tree. You go deep, hit a dead end or find a solution, then undo the last choice and try the next branch.

Understanding what triggers a backtrack is critical. You backtrack when: you have built a complete solution (record it, then backtrack to find more), or when continuing from the current state can never yield a valid solution (pruning). The efficiency of a backtracking solution is almost entirely determined by how aggressively and correctly you prune.

Every backtracking problem follows the same three-step skeleton: choose, explore, unchoose. In code, this translates to a recursive function backtrack(path, choices) that first checks if path represents a complete valid solution (if so, add to results), then iterates over available choices, makes a choice (mutates path and/or the choices set), recurses, and undoes the choice after the recursion returns. This undo step — the "unchoose" — is what restores state so the next iteration starts clean.

The template handles all cases uniformly because the only parts that change between problems are: what constitutes a valid "choice" at each step (the pruning condition), and what constitutes a "complete solution" (the base case). The recursion structure, the choose/recurse/unchoose loop, and the result collection are identical across permutations, combinations, subsets, and constraint satisfaction.

A common implementation error is forgetting the unchoose step or placing it in the wrong location. The unchoose must happen after the recursive call returns, not before it. If you push an element onto path before recursing, you must pop it after recursing. If you mark a cell as visited before recursing, you must unmark it after. Consistent symmetric choice/unchoose pairs are the hallmark of correct backtracking code.

Permutations are the prototypical backtracking problem: order matters, every element is used exactly once, and there are n! results for an input of size n. The key insight is that at each level of the decision tree, you choose from elements that are not yet in the current path. The standard implementation uses a boolean "used" array (or a set) to track which elements are already on the path, and at each recursive call iterates over all elements, skipping those already used.

The decision tree for permutations of [1, 2, 3] has 3 choices at the root, 2 choices at depth 1, and 1 choice at depth 2 — matching the n! count. The base case fires when the path length equals the input length, at which point you have a complete permutation. This "path.length === n" base case is the most common form for permutation-style problems.

For problems with duplicate elements (LeetCode 47 — Permutations II), sort the input first and add a pruning condition: skip element i if nums[i] === nums[i-1] and nums[i-1] is not currently in use. This prevents generating duplicate permutations by ensuring that among duplicate values, you always use the leftmost available copy first.

Combinations and subsets are the complement of permutations: order does not matter. The mechanism for enforcing "no order duplicates" is a start index parameter. Instead of choosing from all unused elements at each level, you choose only from elements at index start or later. This ensures that you never add an element that appears earlier in the input than the last element you added, which eliminates ordering duplicates without needing a used array.

Subsets and combinations use the same backtracking skeleton with different collection conditions. For subsets (LeetCode 78), you record path at every single node of the decision tree — including the empty path at the root. For combinations (LeetCode 77 — choose k elements), you record path only when path.length === k (target depth). Combination Sum (LeetCode 39) is a variant where you can reuse elements: the start index on the recursive call stays at i (not i+1), allowing re-selection of the same element.

Handling duplicates in subsets (LeetCode 90) follows the same pattern as Permutations II: sort first, then skip nums[i] if i > start and nums[i] === nums[i-1]. The i > start condition prevents skipping the very first occurrence within a given recursive call (you must try the value at least once), while eliminating all subsequent occurrences of the same value at the same tree depth.

Constraint satisfaction problems like N-Queens (LeetCode 51) and Sudoku Solver (LeetCode 37) are backtracking problems where the "choices" at each step are heavily restricted by problem rules. For N-Queens, placing a queen in column c at row r is only valid if no previously placed queen shares the same column, diagonal, or anti-diagonal. The backtracking structure is identical — iterate over columns, check if the placement is valid, place, recurse to the next row, remove — but the validity check is the heart of the solution.

The key to efficient constraint satisfaction backtracking is O(1) constraint checking. For N-Queens, maintain three sets: one for occupied columns, one for occupied diagonals (row - col is constant along a diagonal), and one for occupied anti-diagonals (row + col is constant). Before placing a queen, check all three sets in O(1) rather than scanning the board. For Sudoku, maintain sets for each row, column, and 3x3 box — again O(1) per check, O(1) update.

Pruning in constraint satisfaction is more aggressive than in permutations or subsets because the validity check typically eliminates many choices before recursing. N-Queens on an 8x8 board has 8^8 = 16 million possible placements but only 92 valid solutions — the pruning ratio exceeds 99.9%. Writing the constraint check correctly and early (before recursing, not after) is what makes constraint satisfaction backtracking tractable for problem sizes used in coding interviews.

Backtracking and dynamic programming are both techniques for solving problems with overlapping subproblems, but they serve fundamentally different goals. Backtracking enumerates all solutions — it is the right tool when you need every valid arrangement, every valid path, or every valid assignment. Dynamic programming optimizes over solutions — it is the right tool when you need the minimum cost, maximum profit, or number of ways to achieve a goal. The question "do I need all solutions or just the best/count?" is the primary decision fork.

Some problems accept both approaches with different performance characteristics. Word Break II (LeetCode 140) asks for all valid word break strings — backtracking with memoization is appropriate. Coin Change (LeetCode 322) asks for the minimum number of coins — DP is strictly better because backtracking would exponentially re-explore identical subproblems. Partition Equal Subset Sum (LeetCode 416) asks whether a valid partition exists — DP is canonical, but backtracking with pruning also passes on LeetCode test cases.

A practical heuristic: if the problem asks "find all X" or "generate all X," reach for backtracking. If it asks "count the number of ways," try DP first — backtracking generates and counts every individual solution, which is exponentially slower than DP's bottom-up counting. If it asks "find the minimum/maximum," DP almost always dominates.

The recommended backtracking study path starts with the pure enumeration problems that directly map to the template, then moves to problems with pruning conditions, and finishes with constraint satisfaction problems that require O(1) constraint checking. Working through problems in this order builds the template intuition first and layers complexity incrementally rather than confronting constraint management before the core recursion structure is automatic.

The starter problems are Subsets (78) and Permutations (46) — both can be solved with the template almost verbatim. Subsets II (90) and Permutations II (47) add duplicate handling. Combination Sum (39) introduces reuse of elements. Palindrome Partitioning (131) adds a string validity check as the pruning condition. Word Search (79) brings backtracking into a 2D grid context. N-Queens (51) and Sudoku Solver (37) are the full constraint satisfaction problems.

For interview preparation, being able to solve the medium-tier problems fluently — Combination Sum, Palindrome Partitioning, Word Search — is sufficient for most FAANG coding rounds. N-Queens and Sudoku Solver are genuine hard problems that appear in senior-level interviews. Solidify the medium tier first, then tackle the hards as stretch problems once the template is second nature.