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.
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is the backtracking template for solving recursion problems?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”The universal backtracking template: define backtrack(state, choices). If state is a complete solution, add to results and return. For each choice in available choices: if the choice is valid (passes constraints), make the choice (modify state), recursively call backtrack with updated state, undo the choice (restore state — the backtrack step). This generates a decision tree where each node is a partial solution, branches are choices, and leaves are complete solutions or dead ends. The key insight is the undo step: after exploring one branch, restore the state and try the next branch. This systematically explores all possibilities without missing any. Time complexity depends on the problem: permutations O(N!), subsets O(2^N), combinations O(C(N,K)). Pruning (skipping invalid branches early) dramatically reduces the actual running time.”}},{“@type”:”Question”,”name”:”How do you generate all permutations using backtracking?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”For [1,2,3], generate all 6 orderings. At each position, choose which unused element to place. Approach: maintain a used boolean array tracking which elements are placed. For each position, try each unused element: mark it used, place it, recurse for the next position, then unmark it (backtrack). Base case: all positions filled (current permutation length equals N). Swap optimization: instead of a used array, swap elements in place. For position i, swap arr[i] with each element from i to N-1, recurse for position i+1, then swap back. Handling duplicates: sort the array first. At each recursion level, skip an element if it equals the previous tried element. This avoids generating duplicate permutations. Time: O(N * N!) — N! permutations, each takes O(N) to copy to results.”}},{“@type”:”Question”,”name”:”How does backtracking solve the N-Queens problem?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”N-Queens: place N queens on an N x N board so no two queens attack each other (no shared row, column, or diagonal). Backtracking approach: place queens row by row. For each row, try each column position. Constraint check: is this column already occupied? Is this diagonal (row – col) occupied? Is this anti-diagonal (row + col) occupied? Track occupied columns, diagonals, and anti-diagonals in hash sets. If all constraints pass, place the queen and recurse to the next row. If no column works in the current row, backtrack to the previous row and try the next column. Base case: all N rows have queens placed — add the board configuration to results. Time: worst case O(N!) but pruning makes it much faster. For N=8, the algorithm explores far fewer than 8! = 40320 possibilities because most branches are pruned after 2-3 queen placements.”}},{“@type”:”Question”,”name”:”What pruning strategies make backtracking faster?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Pruning eliminates branches that cannot lead to valid solutions: (1) Constraint checking — validate the partial solution before recursing deeper. For N-Queens, check column and diagonal conflicts before placing each queen. (2) Remaining capacity — for combination sum, if the current sum exceeds the target, stop exploring. For combinations of size K, if remaining elements < remaining slots needed, stop. (3) Sorting for duplicate skipping — sort the input. At each recursion level, skip elements equal to the previously tried element. This eliminates duplicate results without maintaining a visited set. (4) Forward checking — before recursing, verify remaining choices can satisfy all constraints. For Sudoku, if placing a digit leaves another cell with zero valid candidates, backtrack immediately rather than discovering the dead end later. (5) Most constrained variable — for constraint satisfaction (Sudoku), pick the variable (cell) with the fewest valid values first. This maximizes pruning by failing fast. Good pruning is the difference between a solution that times out and one that runs in milliseconds."}}]}