Backtracking is the go-to technique for problems that require exploring all possible solutions: generating permutations, finding combinations, solving puzzles, and navigating constraint satisfaction problems. This guide covers the backtracking template, core patterns, pruning strategies, and the most common interview problems — giving you a systematic approach to these questions.
The Backtracking Template
Backtracking explores the solution space by building candidates incrementally and abandoning (backtracking) a candidate as soon as it is determined to be invalid. Template: define backtrack(current_state, choices): if current_state is a complete solution, add to results. For each choice in available choices: if choice is valid (passes constraints), make the choice (modify state), recurse: backtrack(updated_state, remaining_choices), undo the choice (restore state — this is the “backtracking” step). This template generates a decision tree. Each node is a partial solution. Branches are choices. Leaves are complete solutions or dead ends. The time complexity depends on the branching factor (number of choices at each step) and the depth (number of decisions). For generating all permutations of N elements: branching factor = N, N-1, N-2, … 1. Total leaves = N!. For combinations: branching factor is smaller (choose or skip each element). Total subsets = 2^N.
Pattern 1: Subsets (Power Set)
Generate all subsets of a set. For [1,2,3]: [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]. At each position, you make a binary choice: include the element or skip it. Backtracking approach: for each element starting from index i, either include it in the current subset and recurse with i+1, or skip it and recurse with i+1. Add the current subset to results at every step (not just at the end — every partial subset is valid). Time: O(2^N) subsets, each takes O(N) to copy. Total: O(N * 2^N). Variants: subsets with duplicates (sort first, skip consecutive duplicates when the previous duplicate was not included), subsets that sum to a target (add a sum constraint — prune branches where the running sum exceeds the target). The subset pattern is the simplest backtracking pattern and the foundation for combinations and partition problems.
Pattern 2: Permutations
Generate all orderings of a set. For [1,2,3]: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]. At each position, choose which unused element to place. Backtracking approach: maintain a “used” boolean array. For position i, try each unused element: mark it as used, place it at position i, recurse for position i+1, then unmark it (backtrack). Base case: all positions filled (current permutation length == N). Time: O(N!) permutations, each O(N) to copy. Total: O(N * N!). Swap-based optimization: instead of a used array, swap elements in-place. For position i, swap elements[i] with each element from index i to N-1, recurse, then swap back. This avoids the used array and is slightly more cache-friendly. Variants: permutations with duplicates (sort first, skip elements that are equal to the previous tried element at the same position), next permutation (find the next lexicographically larger permutation without generating all).
Pattern 3: Combinations
Choose K elements from N. For [1,2,3,4] with K=2: [1,2], [1,3], [1,4], [2,3], [2,4], [3,4]. Similar to subsets but only add to results when the subset size equals K. Backtracking approach: starting from index i, for each element from i to N-1: include it, recurse with i+1 and remaining K-1, then remove it (backtrack). Prune: if remaining elements (N – i) < remaining K, stop (not enough elements left to complete the combination). Time: O(C(N,K)) combinations, each O(K) to copy. Combination Sum: given candidates and a target, find all combinations that sum to target. Candidates can be reused. Modify the combination pattern: instead of moving to i+1 after including an element, stay at i (allow reuse). Add a sum constraint: if current sum exceeds target, prune. If current sum equals target, add to results. Combination Sum II: each candidate used at most once. Move to i+1 after including. Skip duplicates (same as subsets with duplicates).
Pattern 4: Constraint Satisfaction (N-Queens, Sudoku)
Constraint satisfaction problems place elements subject to rules. N-Queens: place N queens on an N x N board such that no two queens threaten each other (no same row, column, or diagonal). Backtracking: place queens row by row. For each row, try each column. Check constraints: is this column already used? Is this diagonal already used? Track used columns, diagonals (row – col), and anti-diagonals (row + col) in sets. If valid, place the queen and recurse to the next row. If no column works, backtrack to the previous row and try the next column. Time: worst case O(N!), but pruning makes it much faster in practice. Sudoku solver: for each empty cell, try digits 1-9. Check constraints: no duplicate in the same row, column, or 3×3 box. If valid, place the digit and recurse to the next empty cell. If no digit works, backtrack (remove the placed digit, try the next). Optimization: choose the empty cell with the fewest valid candidates (most constrained variable heuristic). This dramatically reduces the search space by pruning early. Word search in a grid: find if a word exists in a 2D grid by following adjacent cells. DFS with backtracking: mark the current cell as visited, recurse in 4 directions for the next character, unmark on backtrack.
Pruning Strategies
Pruning eliminates branches of the search tree that cannot lead to valid solutions, dramatically reducing the time complexity. Strategies: (1) Constraint checking — validate the partial solution at each step. If the current state violates a constraint, do not recurse deeper. N-Queens checks column and diagonal constraints before placing each queen. (2) Bound estimation — for optimization problems, estimate the best possible result from the current state. If the estimate cannot beat the current best, prune. Branch-and-bound uses this for knapsack and scheduling problems. (3) Sorting for duplicate skipping — sort the input array. When iterating over choices, skip elements equal to the previous choice at the same recursion level. This eliminates duplicate subsets/combinations without checking against a seen set. (4) Remaining capacity check — for combination sum, if the current sum already exceeds the target, prune. For combinations of size K, if remaining elements < remaining slots, prune. (5) Forward checking — before recursing, verify that remaining choices can satisfy all constraints. For Sudoku, if placing a digit leaves an empty cell with zero valid candidates, backtrack immediately. Good pruning is the difference between a solution that times out and one that runs in milliseconds.