Chapter 5: Backtracking

Week 5

Explore systematic search through decision spaces using backtracking. Learn how to enumerate subsets, combinations, and permutations by building partial solutions incrementally, pruning invalid branches early, and applying memoization when subproblems overlap.

Topics: 8
Demos: 5
Videos: 3
Min read: 34

Chapter Overview

Backtracking is a refined form of brute-force search. Instead of generating every possible solution and then checking validity, backtracking builds solutions incrementally---placing one element at a time---and abandons a partial solution as soon as it determines that it cannot possibly lead to a valid answer.

The key idea is a state-space tree: each node represents a partial solution, each edge represents a decision (include an element, pick a digit, place a queen), and each leaf is a complete candidate. DFS traverses this tree, and pruning cuts off entire subtrees when constraints are violated, dramatically reducing the search space.

Backtracking problems share a common template: choose a candidate, recurse with the updated state, then undo the choice (backtrack) before trying the next candidate. Mastering this template unlocks an entire class of interview problems---from generating subsets and permutations to solving constraint-satisfaction puzzles like N-queens and Sudoku.

This chapter covers:

State-space trees: Visualizing the decision tree and understanding how DFS explores it
Combinatorial generation: Subsets, combinations, and permutations using systematic enumeration
Pruning strategies: Cutting invalid branches early to avoid unnecessary work
Classic backtracking problems: Phone letter combinations, valid parentheses, and word break
Deduplication: Handling duplicate elements without producing duplicate results

Chapter Roadmap

Click any topic to jump in

Explainer videoInteractive demo

DFS with States

Every backtracking algorithm is a DFS over a state-space tree — nodes are partial solutions, edges are choices.

State-Space TreeBacktracking Template

From template to problem shapes

Combinations and permutations are the two fundamental shapes that map to the DFS template.

Combinations & Permutations

The two canonical shapes: choose $k$ from $n$ (order-free) and order $n$ items (order matters).

Combinations (Choose k from n)Permutations (All Orderings)

Pruning

Cut branches that cannot satisfy constraints — turns exponential search spaces into tractable ones.

Early Termination and Constraint CheckingN-Queens Constraint Propagation

Controlling the explosion

Letter Combinations

Generate the Cartesian product of digit-to-letter sets — a clean application of the combinatorial template.

Digit-to-Letter MappingIterative Cartesian Product Alternative

Generate Parentheses

Count of valid strings is the $n$-th Catalan number; the backtrack tree grows with constraint-guided pruning.

Open/Close Counting ConstraintCatalan Numbers and Counting

Applying the template

Each classic problem picks a different strategy — unrestricted product, constraint-driven, or choice-tracking.

Permutation Strategies

Two equivalent approaches — visited-array tracking versus in-place swap — with the same $\Theta(n \cdot n!)$ cost.

Visited-Array PermutationsSwap-Based In-Place Permutations

Memoization

When the backtrack tree has overlapping subproblems, caching collapses exponential work to polynomial.

Overlapping Subproblems in BacktrackingMemoized Word Break

From search to DP

Deduplication

Sort and skip — the standard way to avoid generating the same subset or permutation twice.

Sort and Skip PatternPermutations with Duplicates

Topics

8 topics in this chapter

A pizza shop offers three toppings, and you want to list every possible pizza, from plain cheese to all three toppings together. With three toppings you can write the eight options by hand, but with twenty toppings there are over a million, and you need a systematic way to produce each one exactly once without missing any.

The previous chapter, Depth First Search & Trees, walked real trees made of node objects. Backtracking walks a tree that is never stored: a state-space tree, where the root is an empty choice, each level decides one thing, such as whether topping i is on the pizza, and each root-to-leaf path is one complete candidate. The same DFS you used on binary trees explores it, carrying a partial solution down and undoing the last decision on the way back up.

We first draw the state-space tree for subsets and count its nodes and leaves, which explains why this kind of search is exponential. Then we distill the choose, explore, unchoose template that every later topic in this chapter reuses, and look at the two bugs that break it most often.

Definition

Backtracking is a depth-first search over a state-space tree whose nodes are partial solutions and whose edges extend a partial solution by one choice. At each node it chooses an option, recurses, and then undoes the choice before trying the next option, so a single mutable state is reused across the whole search. Leaves, or other accepted nodes, are recorded as solutions.

In this topic

1State-Space Tree
2Backtracking Template

1 of 2

State-Space Tree

A state-space tree is an abstract tree where each path from root to leaf represents a sequence of decisions that builds one complete candidate solution. The root is the empty state (no decisions made). At each level, you decide what to do with the next element---include it, exclude it, or choose from a set of options. DFS explores this tree, visiting every path. The total number of leaves equals the total number of candidate solutions.

Mathematical Intuition

A backtracking algorithm is a DFS over a state-space tree whose nodes are partial solutions and whose edges represent extending a partial solution by one choice. If each node has at most $b$ children (branching factor) and depth is at most $d$ , the tree has at most $b^d$ leaves and $\Theta(b^d)$ nodes. Work per node is at least $\Omega(d)$ to copy the state, so total time is $\Omega(d \cdot b^d)$ — inherently exponential without pruning.

Example:

Visualize the state-space tree for generating all subsets of [1, 2, 3].

2 of 2

Backtracking Template

Building a fresh copy of the partial solution at every node wastes time and memory, so backtracking keeps one shared list and edits it in place. Each node repeats three steps. Choose: append a candidate to the shared list. Explore: recurse, so the child sees the extended state. Unchoose: pop the candidate, restoring exactly the state the parent had, before trying the next option. This is the down-and-up flow from DFS on Trees, with state passed down by mutation. Two bugs dominate. Forgetting to unchoose leaks one branch's choices into its siblings, and recording the list without copying it stores a reference that later edits overwrite.

Mathematical Intuition

The template is: $(1)$ if state is a solution, record it and return; $(2)$ for each choice, apply it (mutate state), recurse, undo it (restore state). Undoing is what makes 'backtracking' — it reuses one mutable buffer across the entire traversal for $O(d)$ extra memory. The total time remains $\Theta(|\text{tree}| \cdot d)$ but the constants are smaller than building new states.

Example:

Generate all subsets of a list using the backtracking template.

Papers

Golomb, S. W. & Baumert, L. D. — Backtrack Programming (1965, Journal of the ACM)Bitner, J. R. & Reingold, E. M. — Backtrack Programming Techniques (1975, Communications of the ACM)

Blogs

Backtracking — GeeksforGeeks A General Approach to Backtracking Questions — LeetCode Discuss

Definition

A k-combination of n items is an unordered selection of k distinct items, and there are C(n, k) = n! / (k! (n-k)!) of them. A permutation of n items is an ordered arrangement of all of them, and there are n! of them. Backtracking generates combinations by choosing indices in increasing order, and permutations by choosing any unused item at each position.

In this topic

1Combinations (Choose k from n)
2Permutations (All Orderings)

1 of 2

Combinations (Choose k from n)

A combination selects k elements from n without regard to order. There are C(n, k) = n! / (k!(n-k)!) such selections. The backtracking approach iterates from a start index forward, ensuring elements are chosen in increasing order so that {1,2,3} is generated but {3,1,2} is not. Once the current selection reaches size k, it is recorded and the recursion stops. Pruning is possible: if fewer than k - len(current) elements remain, that branch cannot produce a valid combination and should be skipped.

Mathematical Intuition

The number of $k$ -combinations from $n$ items is $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ . The recursive identity $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ maps directly to 'include or exclude the current item', yielding a backtracking tree with exactly $\binom{n}{k}$ leaves. Each leaf does $O(k)$ work to copy, so total time is $\Theta(k \cdot \binom{n}{k})$ .

Example:

Generate all combinations of 2 elements from [1, 2, 3, 4].

2 of 2

Permutations (All Orderings)

In a permutation, position matters, so [1, 2, 3] and [3, 2, 1] are different answers, and the forward-only start index used for combinations would miss most of them. Instead, every position may take any element that has not been placed yet. A boolean array used, where used[i] is True while nums[i] sits in the current arrangement, answers that question in O(1). At depth d there are n - d choices, so the tree has n! leaves. The unchoose step must reset both the list and the flag. Forgetting the flag leaves the element marked as used forever, so every later branch skips it and loses permutations.

Mathematical Intuition

There are $n!$ permutations of $n$ distinct items. Backtracking places one item per level: level 0 has $n$ choices, level 1 has $n-1$ , etc., giving $n \cdot (n-1) \cdots 1 = n!$ leaves. Copying each into the output costs $\Theta(n)$ , so total time is $\Theta(n \cdot n!)$ . This is asymptotically tight because the output itself has that size.

Example:

Generate all permutations of [1, 2, 3].

Papers

Ehrlich, G. — Loopless Algorithms for Generating Permutations, Combinations, and Other Combinatorial Configurations (1973, Journal of the ACM)

Blogs

Combinations — NeetCode Permutations — NeetCode

Definition

Pruning is the practice, during backtracking, of abandoning a partial solution as soon as a check shows that no completion of it can satisfy the constraints. The entire subtree below that node is skipped. Pruning never changes the set of solutions found, only the number of nodes visited, provided the check never rejects a partial solution that could still succeed.

In this topic

1Early Termination and Constraint Checking
2N-Queens Constraint Propagation

1 of 2

Early Termination and Constraint Checking

Early termination means stopping recursion the moment a constraint is violated, rather than continuing to build an invalid solution. At each step, you check whether the current partial solution can still become valid. If not, you return immediately without exploring deeper. The earlier you detect invalidity, the more subtrees you skip. Common constraints include: value ranges, uniqueness, adjacency rules, and capacity limits. Effective pruning reduces exponential search spaces to manageable sizes.

Mathematical Intuition

Pruning discards any subtree whose partial solution already violates a constraint. If a constraint on partial state $s$ can be checked in $O(c)$ and eliminates an entire subtree of size $k$ , pruning saves $\Theta(k)$ work at cost $O(c)$ — a huge win when $k \gg c$ . The canonical example is N-Queens: without pruning $\Theta(n^n)$ , with constraint checking about $\Theta(n!)$ .

Example:

Find all subsets of [2, 5, 3, 8, 1] that sum to exactly 10. Use pruning to skip subsets whose partial sum already exceeds 10.

2 of 2

N-Queens Constraint Propagation

The N-queens problem places N queens on an N x N board such that no two share a row, column, or diagonal. Since each row must contain exactly one queen, we place one queen per row and track three sets: occupied columns, occupied main diagonals (row - col is constant), and occupied anti-diagonals (row + col is constant). Before placing a queen, we check all three sets. If any is occupied, we prune that branch. This reduces the search from N^N to roughly N! possibilities, with further pruning cutting it even more.

Mathematical Intuition

Placing one queen per row already shrinks the raw space from $n^n$ placements to the permutation tree, which for $n = 8$ has $\sum_{d=0}^{8} \frac{8!}{(8-d)!} = 109{,}601$ nodes. Adding the two diagonal sets, $r - c$ and $r + c$ , cuts the search to 2,057 nodes for all 92 solutions. Each check is $O(1)$ , so the total cost is proportional to the nodes visited: still exponential in $n$ , but small enough to solve boards up to about $n = 15$ exhaustively.

Example:

Solve the 4-queens problem and print all valid board configurations.

Papers

Knuth, D. E. — Estimating the Efficiency of Backtrack Programs (1975, Mathematics of Computation)Haralick, R. M. & Elliott, G. L. — Increasing Tree Search Efficiency for Constraint Satisfaction Problems (1980, Artificial Intelligence)

Blogs

N-Queens — NeetCode Pruning in Backtracking — GeeksforGeeks

Definition

Given a string of digits from 2 to 9, the letter-combination problem asks for every string formed by choosing one letter from each digit's keypad group, in digit order. The answer is the Cartesian product of those groups. Its size is the product of the group sizes, at most 4^n for n digits, so any algorithm needs time at least proportional to n times that count.

In this topic

1Digit-to-Letter Mapping
2Iterative Cartesian Product Alternative

1 of 2

Digit-to-Letter Mapping

The classic phone keypad maps each digit 2-9 to a group of letters: 2->abc, 3->def, 4->ghi, 5->jkl, 6->mno, 7->pqrs, 8->tuv, 9->wxyz. Given a string of digits like "23", the task is to produce all strings formed by choosing one letter from each digit's group. The number of combinations is the product of the group sizes: for "23" that is 3 x 3 = 9 strings. This is a direct application of the backtracking template where each level of recursion processes one digit.

Mathematical Intuition

The phone mapping assigns $3$ or $4$ letters per digit. For an $n$ -digit input, the output has $\prod_{i=1}^{n} |d_i|$ strings, bounded by $4^n$ . Backtracking has depth $n$ , branching factor up to $4$ , so the state-space tree has $\Theta(4^n)$ leaves and total work $\Theta(n \cdot 4^n)$ — dominated by the size of the answer.

Example:

Generate all letter combinations for the digit string "23".

2 of 2

Iterative Cartesian Product Alternative

The phone letter problem is mathematically a Cartesian product of the letter groups for each digit. While backtracking solves it recursively, you can also solve it iteratively: start with an empty string, and for each digit, append every possible letter to every existing partial result. This produces the same output and illustrates that backtracking and iterative expansion are two views of the same combinatorial process. Python's itertools.product captures this pattern directly.

Mathematical Intuition

The iterative equivalent starts with $\{$ '' $\}$ and, for each digit $d$ , replaces the current list with $\{s + c : s \in \text{list}, c \in \text{letters}(d)\}$ . This is exactly one level of the BFS version of the tree, producing the same $\prod |d_i|$ strings with the same asymptotic cost but different memory profile — $\Theta(\prod |d_i|)$ queue size versus $\Theta(n)$ stack.

Example:

Solve the phone letter problem iteratively using list expansion.

Papers

Bitner, J. R. & Reingold, E. M. — Backtrack Programming Techniques (1975, Communications of the ACM)

Blogs

Letter Combinations of a Phone Number — NeetCode Letter Combinations — LeetCode Editorial

Definition

A string of n opening and n closing parentheses is well formed if every prefix contains at least as many opening as closing parentheses. Backtracking generates exactly these strings by adding "(" while fewer than n are used and ")" while fewer closing than opening brackets are placed. There are C_n = C(2n, n) / (n + 1) such strings, the n-th Catalan number.

In this topic

1Open/Close Counting Constraint
2Catalan Numbers and Counting

1 of 2

Open/Close Counting Constraint

Valid parentheses strings satisfy two rules at every prefix: (1) the number of open parentheses is at most n, and (2) the number of close parentheses never exceeds the number of opens. These two rules serve as pruning conditions in the backtracking tree. If open_count < n, we can add '('. If close_count < open_count, we can add ')'. When both counts reach n, the string is complete and guaranteed to be valid. The total number of valid strings is the nth Catalan number: C(n) = (2n)! / ((n+1)! * n!).

Mathematical Intuition

A string of $n$ open and $n$ close parens is valid iff at every prefix, $\text{open} \ge \text{close}$ , and the totals are equal. Backtracking keeps counters: you can add '(' while $\text{open} < n$ and ')' while $\text{close} < \text{open}$ . This constraint prunes most of the $\binom{2n}{n}$ possible strings down to the Catalan count — a huge saving.

Example:

Generate all valid parentheses strings for n = 3.

2 of 2

Catalan Numbers and Counting

The number of valid parenthesizations of n pairs is the nth Catalan number: C(n) = C(2n, n) / (n+1). The sequence starts 1, 1, 2, 5, 14, 42, 132, 429, ... Catalan numbers appear in many combinatorial problems: the number of binary search trees with n nodes, the number of ways to triangulate a polygon, and the number of paths on a grid that stay below the diagonal. Understanding this count helps you verify your backtracking solution produces the correct number of results.

Mathematical Intuition

The number of valid parenthesis strings of length $2n$ is the $n$ -th Catalan number $C_n = \frac{1}{n+1}\binom{2n}{n} \sim \frac{4^n}{n^{3/2} \sqrt{\pi}}$ . Generating each takes $\Theta(n)$ to copy, so total time is $\Theta(n \cdot C_n) = \Theta(\frac{4^n}{\sqrt{n}})$ . Catalan numbers also count balanced binary trees, triangulations of polygons, and Dyck paths — all isomorphic to parenthesis strings.

Example:

Verify that the parentheses generator produces C(n) results for n = 1 through 6.

Papers

Ruskey, F. & Hu, T. C. — Generating Binary Trees Lexicographically (1977, SIAM Journal on Computing)

Blogs

Generate Parentheses — NeetCode Catalan Number — Wikipedia

Definition

A permutation of n distinct items is an ordering of all of them, and there are n! permutations. Backtracking fills one position per level. The visited-array method picks any unused item and records its use in a boolean array; the swap method swaps each candidate into the current position of the array itself. Both run in Theta(n * n!) time, including copying the output.

In this topic

1Visited-Array Permutations
2Swap-Based In-Place Permutations

1 of 2

Visited-Array Permutations

The visited-array approach maintains a boolean array where used[i] indicates that nums[i] has already been placed in the current permutation. At each recursive level, we iterate over all elements and skip those already used. This produces permutations in lexicographic order when the input is sorted. The space overhead is O(n) for the used array plus O(n) for the current permutation list, plus O(n) recursion depth---total O(n) auxiliary space beyond the output.

Mathematical Intuition

A boolean array $\text{used}[0..n-1]$ tracks which elements are already in the current permutation prefix. At depth $d$ , there are $n - d$ unused choices, giving the total number of explored states as $\sum_{d=0}^{n} \frac{n!}{(n-d)!} = \Theta(n!)$ . Each state does $O(1)$ work to set/clear a flag, so per-permutation overhead is $\Theta(n)$ — identical to the swap method asymptotically.

Example:

Generate all permutations of ['a', 'b', 'c'] using the visited-array approach.

2 of 2

Swap-Based In-Place Permutations

The swap-based approach fixes one position at a time by swapping elements. To fill position first, swap each element from positions first through n-1 into position first, recurse to fill position first+1, then swap back. This uses O(1) extra space (beyond the recursion stack) because the permutation is built in place within the input array. The trade-off is that permutations are not generated in lexicographic order, and handling duplicates requires extra care.

Mathematical Intuition

Instead of tracking visited elements, swap element $i$ with position $d$ to 'select' it. This uses $O(1)$ extra space beyond the mutable array and the call stack. Total time $\Theta(n \cdot n!)$ matches the visited-array method. Downside: the permutations come out in a different order, and if ordering matters (sorted output) you must collect and sort, losing the in-place benefit.

Example:

Generate all permutations of [1, 2, 3] using the swap method.

Papers

Sedgewick, R. — Permutation Generation Methods (1977, ACM Computing Surveys)Heap, B. R. — Permutations by Interchanges (1963, The Computer Journal)

Blogs

Permutations — NeetCode Heap's Algorithm — Wikipedia

Definition

Memoization caches the result of a recursive function for each distinct argument, so each subproblem is solved at most once. It helps whenever different paths of a search reach identical states, which is called overlapping subproblems. In Word Break, the state is the start index of the remaining suffix, so there are n + 1 states, and the memoized search runs in polynomial time.

In this topic

1Overlapping Subproblems in Backtracking
2Memoized Word Break

1 of 2

Overlapping Subproblems in Backtracking

Overlapping subproblems occur when the same recursive subproblem is encountered multiple times during exploration. In standard backtracking, each call is independent because the state changes at each step. But in problems like Word Break, the remaining string after different valid splits can be identical. Without memoization, the same suffix is re-examined from scratch, leading to exponential time. Memoization turns this into a polynomial-time solution by ensuring each unique suffix is solved only once.

Mathematical Intuition

A backtracking tree has overlapping subproblems iff distinct paths from the root lead to identical states. For word break, the state is the current suffix — different split histories can reach the same suffix, so naive backtracking is $\Theta(2^n)$ . Identifying overlap is the prerequisite for memoization; without overlap, memoization cannot help.

Example:

Show how Word Break without memoization repeats work on the string 'catsanddog' with dictionary ['cat', 'cats', 'and', 'sand', 'dog'].

2 of 2

Memoized Word Break

By adding a memo dictionary that maps each starting index to its result (True or False), we ensure each index is processed at most once. The first time we reach index i, we compute whether s[i:] can be segmented and store the result. Future calls with the same index return immediately. This reduces the time complexity from O(2^n) to O(n^2 * m) where n is the string length and m is the maximum word length in the dictionary.

Mathematical Intuition

Cache results on $\text{start}$ index (or equivalently, the suffix). There are only $n$ distinct suffixes, so once memoized, each subproblem is solved once. With $n$ states and $O(n \cdot L)$ per state (scanning word lengths up to $L$ ), total time is $\Theta(n^2 \cdot L)$ — a polynomial vs. exponential collapse. This pattern — memoizing over start index — recurs throughout DP on strings.

Example:

Solve Word Break with memoization and compare the call count to the naive version.

Papers

Michie, D. — "Memo" Functions and Machine Learning (1968, Nature)Bellman, R. — On the Theory of Dynamic Programming (1952, Proceedings of the National Academy of Sciences)

Blogs

Word Break — NeetCode Memoization — GeeksforGeeks

Definition

Deduplication in backtracking produces each distinct result exactly once when the input contains repeated values. Sort the input so equal values are adjacent, then skip a candidate that equals the previous candidate at the same tree level. For subsets the test is i > start and nums[i] == nums[i-1]; for permutations it is nums[i] == nums[i-1] and not used[i-1].

In this topic

1Sort and Skip Pattern
2Permutations with Duplicates

1 of 2

Sort and Skip Pattern

The sort + skip deduplication pattern works as follows: (1) Sort the input array so duplicates are adjacent. (2) At each level of the backtracking tree, when iterating over candidates, skip nums[i] if it equals nums[i-1] and i-1 was not selected at this level. The key insight is that if two identical elements could both be chosen, we enforce that the earlier one must be chosen first. This prevents generating the same subset or combination through different orderings of identical elements. The condition varies slightly between subsets (skip if i > start and nums[i] == nums[i-1]) and permutations (skip if nums[i] == nums[i-1] and not used[i-1]).

Mathematical Intuition

To avoid generating the same subset/permutation twice when the input has duplicates, sort first so equal elements are adjacent. Then, at each choice point, skip the current element if it equals the previous and the previous was not used in this branch. Sorting is $\Theta(n \log n)$ upfront; the skip rule keeps the output unique without using a hash set, preserving the asymptotic cost of the raw backtracking.

Example:

Generate all unique subsets of [1, 2, 2] without duplicates.

2 of 2

Permutations with Duplicates

For permutations with duplicates, the skip condition is slightly different: skip nums[i] if nums[i] == nums[i-1] and used[i-1] is False. The reasoning: if two elements are identical, we require the first one to be placed before the second. If the first copy is not yet used (used[i-1] is False), then placing the second copy would create a duplicate permutation---the same arrangement was already generated when the first copy was placed at this position. Sorting ensures duplicates are adjacent so this check works correctly.

Mathematical Intuition

For a multiset with counts $c_1, c_2, \dots, c_k$ , the number of distinct permutations is $\frac{n!}{c_1! \cdot c_2! \cdots c_k!}$ — the multinomial coefficient. The sort-and-skip trick ensures backtracking generates exactly this count, with no duplicates produced and discarded. Without skipping, you would produce $n!$ and dedupe afterwards — the same answer at much higher cost.

Example:

Generate all unique permutations of [1, 1, 2] without duplicates.

Papers

Williams, A. — Loopless Generation of Multiset Permutations using a Constant Number of Variables by Prefix Shifts (2009, SODA)

Blogs

Subsets II — NeetCode Permutations II — LeetCode Editorial

DFS with States

Combinations & Permutations

Pruning

Letter Combinations

Generate Parentheses

Permutation Strategies

Memoization

Deduplication

8 topics in this chapter

DFS with States

Definition

In this topic

State-Space Tree

Backtracking Template

Related Problems on PixelBank

Combinatorial Search

Definition

In this topic

Combinations (Choose k from n)

Permutations (All Orderings)

Related Problems on PixelBank

Pruning

Definition

In this topic

Early Termination and Constraint Checking

N-Queens Constraint Propagation

Related Problems on PixelBank

Letter Combinations of Phone

Definition

In this topic

Digit-to-Letter Mapping

Iterative Cartesian Product Alternative

Related Problems on PixelBank

Generate Parentheses

Definition

In this topic

Open/Close Counting Constraint

Catalan Numbers and Counting

Related Problems on PixelBank

Permutations

Definition

In this topic

Visited-Array Permutations

Swap-Based In-Place Permutations

Related Problems on PixelBank

Memoization & Word Break

Definition

In this topic

Overlapping Subproblems in Backtracking

Memoized Word Break

Related Problems on PixelBank

Deduplication

Definition

In this topic

Sort and Skip Pattern

Permutations with Duplicates

Related Problems on PixelBank