Backtracking

What Is Backtracking?

Backtracking is DFS through a decision tree you never explicitly build. Your recursive function is the traversal. At each node, you make a choice (add an element to the current path), recurse to explore that branch, then undo the choice so the next branch starts clean.

Plain DFS visits nodes in a graph, marking them permanently. Backtracking constructs candidates under constraints, restoring state between branches so elements can be reused on different paths.

Every backtracking problem has three customization points:

• What is "state"? The current partial solution (a path, a board configuration, a set of placed queens).
• What are "valid choices"? Which elements can extend the current state (remaining numbers, valid grid directions, safe columns).
• When is state a "solution"? When to collect the current state as a result (at every node for subsets, at depth k for combinations, at depth n for permutations).

Permutations vs Combinations vs Subsets

Whether order matters in the output changes everything about the implementation.

Subsets

Given an array of distinct integers, return all possible subsets. For input [1, 2, 3], the answer is eight subsets: [], [1], [2], [3], [1,2], [1,3], [2,3], and [1,2,3]. Notice that the empty set counts and that [1,2] and [2,1] are the same subset, so you only generate [1,2]. That observation about ordering is what shapes the entire implementation.

Model this as a decision tree where each level corresponds to one element in the array. At every node, the branches represent choosing one of the remaining elements to include next. The key constraint is that we enforce an ordering: once we consider element at index 2, we never go back to index 0 or 1 in that branch. This is what the start parameter does. By only considering elements from start onward, we guarantee that [1,2] is generated but [2,1] is not, because after choosing 2 at index 1, the recursion only looks at index 2 and beyond.

The most distinctive feature of subsets compared to other backtracking problems is when results get collected. In permutations you collect only at the leaves (when the path has all n elements). In combinations you collect only at depth k. In subsets, every single node in the tree is a valid result, including the root (the empty set). That means the collection line goes before the for-loop, not inside any length check. The root collects [], the node after choosing 1 collects [1], the node after choosing 1 then 2 collects [1,2], and so on. Every partial path is a valid subset.

Why are there exactly 2^n subsets? At each of the n elements, you have two choices: include it or skip it. That gives 2 × 2 × ... × 2 = 2^n total combinations. The decision tree captures this: each level offers branches for including each remaining element, and the structure naturally enumerates all 2^n possibilities without repetition.

The diagram above traces the full [1,2,3] traversal step by step, showing how each node collects a result before exploring deeper. Each pop restores the path so sibling branches start clean.

The time complexity is O(n · 2^n). There are 2^n nodes in the tree, and at each node we copy the current path into result, which costs O(n) in the worst case. The recursion stack depth is n, so space is O(n) excluding the output. This is optimal because you cannot produce 2^n results of size up to n in less time.

Combinations

Given two integers n and k, return all combinations of k numbers chosen from 1 to n. For n=4 and k=2, the answer is [1,2], [1,3], [1,4], [2,3], [2,4], [3,4], six pairs total. Order does not matter, so [2,1] is the same as [1,2] and should not appear separately. If you think of this in terms of the subsets tree, combinations are exactly the nodes that happen to live at depth k. Every other node gets ignored.

The code is nearly identical to subsets with one addition: a base case that collects and returns when len(path) == k. In subsets, every node is a valid result so there is no base case check. In combinations, only nodes at depth k matter, so you add an if-check at the top of the recursive function. The return after collecting is not optional. Without it, the function continues into the for-loop and keeps adding elements past depth k, producing results of length k+1, k+2, and so on. The return is what tells the recursion "this branch is complete, stop going deeper."

The loop range and the recursive argument are identical to subsets. We loop from start to n, passing i+1 to enforce the same ordering constraint that prevents generating [2,1] after [1,2]. The only difference is that the tree gets pruned at depth k instead of being explored all the way to the leaves. This means the recursion tree is shallower: at most k levels deep instead of n levels, which directly affects the complexity.

Walk through n=4, k=2 to see the pruning in action. The root calls backtrack(1, []). The loop picks 1, recursing to backtrack(2, [1]). That call's loop picks 2, recursing to backtrack(3, [1,2]). Now len(path)==2==k, so [1,2] is collected and we return immediately, never entering the loop. Back at [1], the loop continues with 3 to produce [1,3] and 4 to produce [1,4]. Then back at the root, the loop picks 2, and its children produce [2,3] and [2,4]. Finally 3 produces [3,4], and 4 alone at depth 1 cannot reach depth 2 because there are no elements after 4. The tree never goes deeper than 2 levels.

The time complexity is O(k · C(n,k)). There are C(n,k) results, each of length k, and copying each into result costs O(k). The recursion stack depth is at most k. This is output-sensitive: you cannot produce C(n,k) results of size k in less time.

Permutations

Given an array of distinct integers like [1, 2, 3], return all possible orderings. The answer is six permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]. The critical difference from subsets and combinations is that order matters. [1,2] and [2,1] are the same subset but different permutations, and both must appear in the result.

This means a start index will not work. In subsets, passing start and looping from start onward prevents generating [2,1] after [1,2], which is exactly what we want because they represent the same subset. But in permutations, [2,1] is a distinct valid result that must appear. If we used a start index, we would only generate orderings where indices are increasing, which is just subsets. Instead, we loop from 0 at every recursion level, giving every element a chance to appear at every position. The mechanism that prevents using the same element twice in a single permutation is a boolean array called used[].

Think about the branching factor at each level of the tree. At depth 0, all n elements are available, so there are n branches. At depth 1, one element is used, leaving n-1 branches. At depth 2, two are used, leaving n-2. This continues down to depth n-1, which has exactly 1 branch. The total number of leaves is n × (n-1) × (n-2) × ... × 1 = n!, which is exactly the number of permutations. This is why permutations grow factorially while subsets grow exponentially.

Results are collected only at the leaves, when len(path) == n. Unlike subsets where every partial path is a valid result, a permutation must include every element exactly once. A partial path like [1,2] is not a valid permutation of [1,2,3] because it is missing 3. So the collection happens inside a base case check at the top of the function, and the return after collecting prevents the loop from running (there are no unused elements left anyway, but the return makes the intent explicit).

The diagram above traces how used[] toggles on choose and unchoose, showing the available elements shrinking at each depth and restoring on backtrack.

The time complexity is O(n · n!). There are n! leaves (permutations), and at each leaf we copy a path of length n, costing O(n). The recursion stack depth is n. This is optimal because producing n! results of length n requires at least O(n · n!) work.

Handling Duplicates

When the input contains duplicate elements, the same combination or subset can be generated multiple times through different index choices. The fix: sort the input, then skip an element if it equals the previous one at the same recursion level.

Subsets II / Combination Sum II Pattern

The diagram above traces [1,2,2] step by step, showing which branches the skip condition prunes and which survive. The key insight: the condition uses i > start rather than i > 0, so the first element at each recursion level is always allowed, even if it equals the previous element in the sorted array. This means [1,2,2] is correctly generated (the second 2 is the first choice at its level, so i > start is false and the skip does not fire), while duplicate subtrees at the same level are pruned.

Permutations II

Given [1,1,2], there are three unique permutations: [1,1,2], [1,2,1], [2,1,1]. The diagram above shows which branches the skip condition prunes and why. The i > start trick from Subsets II does not work here because permutations loop from 0, not from a start index. Instead, the approach is: sort the array, then skip index i if nums[i] == nums[i-1] and not used[i-1]. This forces identical values to be placed in left-to-right index order, producing exactly one copy of each permutation.

The code sorts the input first, then uses the standard permutation template with one added skip. The used[i] check on line 7 prevents reusing the same index in a single path (same as regular permutations). The second condition on lines 9-10 handles the duplicate skipping. Everything else is identical to the standard permutation code: loop from 0, set used[i]=True, recurse, pop, set used[i]=False.

State Management and the Undo Step

The most common backtracking bug is saving a reference instead of a copy. In Python, result.append(path) does not save the current contents of path. It saves a reference to the list object. Since path is mutated by append and pop, every entry in result ends up pointing to the same empty list.

The Symmetry Rule

Every state mutation before the recursive call must have an exact inverse after it. If you append, you pop. If you mark True, you mark False. If you overwrite a grid cell, you restore the original value.

Pruning: When to Cut Branches

Pruning skips entire subtrees that cannot contain valid solutions. It does not change the worst case complexity, but it often cuts the number of nodes explored by 10x or more.

Safe pruning requires a provable guarantee: no valid solution exists below this branch. Two common reasons to prune:

• Constraint already violated: the current partial solution has exceeded a budget, used too many resources, or violated a constraint that cannot be undone by future choices.
• Cannot possibly satisfy constraint: even in the best case, the remaining elements cannot bring the partial solution to a valid state. For sorted arrays: if the smallest remaining element is too large, all subsequent elements are also too large.

Pruning in Combination Sum

Combination Sum asks: given candidates = [2, 3, 6, 7] and target = 7, find all unique combinations where the chosen numbers sum to 7. Each candidate can be used unlimited times. The answer is [[2, 2, 3], [7]]. This is a backtracking problem because we need all valid combinations, not just one or a count.

The key difference from standard combinations is the recursive argument. In regular combinations, we pass i+1 to prevent reusing the same element. Here, reuse is allowed, so we pass i instead. This means the recursion can pick candidates[i] again in the next call. The start index still increases across siblings (the loop goes from start to end), which prevents generating [3, 2, 2] after [2, 2, 3]. Reuse is vertical (same element deeper in the tree), not horizontal (same element at the same level).

Pruning makes this problem tractable. If we sort candidates first, sorting gives a bound: all elements after index i are at least as large as candidates[i]. When candidates[i] exceeds the remaining target, every subsequent candidate also exceeds it. This means we can break out of the loop entirely, not just skip the current candidate. The difference between break and continue here is dramatic. Continue skips one candidate and moves to the next (which is even larger and will also fail). Break skips all remaining candidates at this level in one step, cutting off an entire subtree.

The diagram above traces candidates=[2,3,6,7] with target=7, showing exactly which branches the break prunes. The critical distinction: break exits the entire loop (not just the current candidate), because with sorted candidates every subsequent value is even larger and will also exceed the budget. Without sorting and pruning, the algorithm still produces correct results but explores many more dead-end branches, recursing all the way to remaining < 0 before failing.

N-Queens Constraint Checking

N-Queens uses three sets for O(1) conflict detection. Columns: which columns have queens. Main diagonals: row-col is constant along each diagonal. Anti-diagonals: row+col is constant. Before placing a queen, check all three sets. If any conflict exists, skip that column.

N-Queens: Constraint Satisfaction

N-Queens asks you to place n queens on an n×n chessboard such that no two queens attack each other. Queens attack along rows, columns, and both diagonals. For n=4, there are exactly two valid arrangements. This is a constraint satisfaction problem (CSP): unlike enumeration problems where you generate all configurations, here most configurations are invalid and the challenge is pruning the search space efficiently.

The backtracking model assigns one recursion level per row. Since each row must have exactly one queen (two queens in the same row would attack each other), we iterate through columns at each level and try placing a queen. The choices at row r are the columns 0 through n-1. The constraints are enforced by three sets that track which columns, main diagonals, and anti-diagonals are already occupied. If a candidate column conflicts with any set, we skip it immediately. This is the pruning that makes N-Queens tractable.

The diagonal math is worth understanding. On a top-left-to-bottom-right diagonal, as you move one step down and one step right, both row and col increase by 1. That means row minus col stays constant along the entire diagonal. For example, cells (0,0), (1,1), (2,2), (3,3) all have row-col = 0. Cells (0,1), (1,2), (2,3) all have row-col = -1. So if we store row-col in a set, checking whether a main diagonal is occupied costs O(1). Anti-diagonals go from top-right to bottom-left: row increases while col decreases, so row plus col stays constant. Cells (0,3), (1,2), (2,1), (3,0) all have row+col = 3. A second set for row+col handles anti-diagonals. Together with the column set, three O(1) lookups replace what would otherwise be an O(n) scan of the board.

The diagram above traces n=4 step by step, showing how the three conflict sets prune invalid placements at each row. Column checking alone reduces the search from O(n^n) to O(n!) because each row eliminates one column. The diagonal constraints reduce the practical runtime further, though the worst-case bound remains O(n!). Space is O(n) for the three sets and the recursion stack.

Word Search: Grid Backtracking

Word Search gives you a 2D grid of characters and a target word, and asks whether the word can be formed by following a path of adjacent cells (up, down, left, right) without revisiting any cell in the same path.

The approach is to try starting from every cell that matches word[0], then explore all four directions for word[1], and so on. When we step onto a cell, we mark it as visited so the same path does not loop back through it. The marking is done in-place by temporarily replacing the cell's character with a sentinel value like '#'. After exploring all four directions from that cell, we restore the original character. This in-place mark-and-restore is the grid equivalent of path.append and path.pop in array-based backtracking.

What makes this backtracking rather than plain DFS is the restoration step. In a standard graph DFS (like connected components or flood fill), once you visit a cell, it stays visited forever. You never need to revisit it because you are exploring reachability, and if a cell is reachable from one path, that is sufficient. But in Word Search, a cell that was part of one failed path must be available for a different path. If you mark (0,2) as visited while searching for "ABCCED" and the search fails along one direction, the cell needs to be unmarked so a different starting path can use it. Without restoration, the algorithm would miss valid paths because cells get permanently blocked by earlier failed attempts.

The outer loop tries every cell as a starting point. For most cells, the very first character check fails immediately (board[r][c] != word[0]) and the call returns False in constant time. Only cells matching the first character proceed deeper. This means the outer loop is cheap in practice even though it visits every cell.

The diagram above traces "ABCCED" on this board step by step, including a wrong-direction attempt that backtracks. When a direction fails, the cell's '#' marker is restored to its original value so sibling directions can use it.

The time complexity is O(m · n · 3^L) where m×n is the board size and L is the word length. Each cell can be a starting point (m·n), and from each cell the search branches into at most 3 directions at each step (not 4, because we cannot go back to the cell we just came from since it is marked '#'). The depth of recursion is at most L, so each starting cell explores at most 3^L paths. Space is O(L) for the recursion stack since the in-place marking avoids a separate visited set.

When Backtracking Breaks

Backtracking generates all valid solutions by exploring every branch of a decision tree. This makes it the right tool when the problem asks for all results. When it asks only for a count, a minimum, or one optimal result, generating all solutions is unnecessary and expensive.

DP is correct when the same subproblem appears repeatedly on different paths through the decision tree. Backtracking solves that subproblem from scratch each time it appears. DP solves it once and reuses the answer. The signal is overlapping subproblems: if two different partial paths can reach the same state and need the same remaining decisions, DP removes the duplicate work. The signal in problem phrasing is usually "count," "minimum," or "maximum" rather than "generate all" or "find all valid."

BFS is correct when the goal is the minimum number of steps. Backtracking explores all paths, including longer ones, before finding a minimum. BFS processes states in increasing distance order, so the first time a target state is reached the path length is already minimal. Problems that ask for fewest moves, shortest transformation, or minimum operations on a graph or grid usually need BFS.

Debugging Backtracking

Time Complexity Analysis

General formula: total work = (number of nodes) x (work per node). For subsets: 2^n nodes, O(n) per node to copy the path, total O(n * 2^n). For permutations: n! leaves, each copies a path of length n, total O(n * n!). The recursion stack depth equals the tree height, at most n.

Pruning reduces the constant factor but does not change worst case asymptotics. N-Queens pruning makes practical runtime much better than n^n, but the worst case remains O(n!).

Practice Problems

Subsets / Combinations

Permutations

Constraint Satisfaction

String Partitioning

Advanced

Reference Templates

Every backtracking enumeration problem is a controlled modification of the subsets template. Subsets collects at every node, uses a start index, and passes i+1. Changing one or two of those choices produces every other variant.

Collect at every node, start index: any subset size is valid.

Collect at depth k only, all results have the same length.

Collect at depth n, loop from 0, used[] prevents reuse in the same path.

Pass i (not i+1) for reuse. Sort + break when overshoot is provable.

Sort + skip when i > start and adjacent values match. Skips duplicates at the same level only.

Sort + skip when not used[i-1]. Enforces index order for identical values.

In-place mark and restore. board[r][c] = '#' acts like path.append.

Row-by-row, O(1) conflict sets replace O(n) board scanning.

Pattern Recap

• Subsets collect at every node. Combinations collect at depth k. Permutations collect at depth n.
• A start index prevents reordered duplicates by restricting the loop to elements after the current position. It is correct for subsets and combinations where order does not matter.
• A used[] array allows all orderings. It is required for permutations where [2,1] and [1,2] are distinct valid results.
• Passing i+1 prevents reuse of the current element. Passing i allows reuse. Combination Sum uses i.
• The sort-plus-skip dedup works because identical elements are adjacent after sorting. i > start restricts the skip to the current recursion level only.
• path.pop() restores the mutable path list. board[r][c] = temp restores the mutable grid. Without restoration, sibling branches inherit state from previous branches.
• Pruning is safe only with a proof that no valid solution lies below the current branch.

Rebuilding the Pattern

When a backtracking problem feels unclear, start from the subsets template and answer three questions. Does the result get collected at every node, or only at a certain depth? Does the loop start at a fixed 0, or at a start parameter that advances? Does the recursive call pass i (reuse the current element) or i+1 (move past it)? Those three answers determine the loop range, the base case, and the recursive argument. Every standard enumeration variant is defined by how it answers those three questions.

The duplicate question comes next. If the input can contain identical values and the output should not repeat, sort the input first. For combination-style problems, add if i > start and nums[i] == nums[i-1]: continue. For permutation-style problems, add if i > 0 and nums[i] == nums[i-1] and not used[i-1]: continue. The condition is asymmetric because i > start works only when there is a start index. Permutations loop from 0 and use the used[] array to distinguish which duplicate occurrence is currently in the path.

The pruning question is about safety. A pruning cut removes an entire subtree. It is safe only when you can prove that no valid solution exists below the current partial state. The two valid proofs are: a constraint is already violated and cannot be repaired by future choices, or the remaining elements cannot bring the partial solution into a valid state even in the best case. If neither proof holds, skip the prune and accept the cost.

The state question applies to every mutation. Every change to shared state before the recursive call must be exactly reversed after it. A mutable path needs pop. A mutable grid cell needs value restoration. A used[] flag needs to be reset to False. A set membership needs removal. The symmetry is not optional. Without it, sibling branches inherit choices from previous branches and produce incorrect results.

Check Your Understanding

Use these questions to check whether you can reason through the pattern without looking at the template.

Take Assessment

12 multiple-choice questions covering choose/explore/unchoose, duplicate handling, pruning, and common bugs. Each question includes an explanation of the correct answer.