Backtracking Patterns

Medium 25 min read

Why Backtracking?

🎲

Systematic Search with Pruning

Backtracking explores all possible solutions by building candidates incrementally and abandoning ("backtracking") as soon as it determines a candidate cannot lead to a valid solution. Think of solving a maze: go forward, hit a wall, go back, try a different path.

✏️

The Universal Template

Almost every backtracking problem follows the same 3-step pattern: Choose (pick an option), Explore (recurse), Unchoose (undo and try next). Master the template and you can solve dozens of problems.

📊

Interview Frequency

Backtracking appears in ~10-15% of coding interviews. Key problems: permutations, combinations, subsets, N-Queens, Sudoku, word search.

The Universal Backtracking Template

Template

The 3-Step Pattern: Choose, Explore, Unchoose

1
Choose: Pick a candidate from the available options and add it to the current path.
2
Explore: Recurse with the updated path. If we reach a valid solution, record it.
3
Unchoose: Remove the candidate from the path (backtrack) and try the next option.
Universal Backtracking Template (Python)
def backtrack(candidates, path, result): # Base case: valid solution found if is_solution(path): result.append(path[:]) # copy the path! return for candidate in candidates: if not is_valid(candidate, path): continue # prune invalid branches # 1. Choose path.append(candidate) # 2. Explore backtrack(next_candidates, path, result) # 3. Unchoose (backtrack) path.pop()

Decision Tree: Permutations of [1, 2, 3]

Visualization
[] [1] [2] [3] [1,2] [1,3] [2,1] [2,3] [3,1] [3,2] [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1] Each leaf = one valid permutation. Total = 3! = 6 permutations. Green nodes = complete solutions. Purple/blue = intermediate states.

Classic Backtracking Problems

Level 2

Problem 1: Permutations (LeetCode 46)

Permutations
def permute(nums): result = [] def backtrack(path, used): if len(path) == len(nums): result.append(path[:]) return for i in range(len(nums)): if used[i]: continue path.append(nums[i]) # Choose used[i] = True backtrack(path, used) # Explore path.pop() # Unchoose used[i] = False backtrack([], [False] * len(nums)) return result print(permute([1,2,3])) # [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Problem 2: Combinations (LeetCode 77)

Combinations -- skip duplicates by starting from index
def combine(n, k): result = [] def backtrack(start, path): if len(path) == k: result.append(path[:]) return for i in range(start, n + 1): path.append(i) # Choose backtrack(i + 1, path) # Explore (i+1 avoids reuse) path.pop() # Unchoose backtrack(1, []) return result print(combine(4, 2)) # [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Problem 3: Subsets (LeetCode 78)

Subsets -- include/exclude pattern
def subsets(nums): result = [] def backtrack(start, path): result.append(path[:]) # every path is a valid subset for i in range(start, len(nums)): path.append(nums[i]) backtrack(i + 1, path) path.pop() backtrack(0, []) return result print(subsets([1,2,3])) # [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

Problem 4: N-Queens (LeetCode 51)

N-Queens -- constraint checking
def solve_n_queens(n): result = [] cols = set() diag1 = set() # row - col diag2 = set() # row + col def backtrack(row, queens): if row == n: board = [] for _, c in sorted(queens): board.append("." * c + "Q" + "." * (n - c - 1)) result.append(board) return for col in range(n): if col in cols or (row - col) in diag1 or (row + col) in diag2: continue # Prune: queen under attack cols.add(col) # Choose diag1.add(row - col) diag2.add(row + col) queens.append((row, col)) backtrack(row + 1, queens) # Explore cols.remove(col) # Unchoose diag1.remove(row - col) diag2.remove(row + col) queens.pop() backtrack(0, []) return result

Problem 5: Word Search (LeetCode 79)

Word Search -- grid backtracking
def exist(board, word): rows, cols = len(board), len(board[0]) def backtrack(r, c, idx): if idx == len(word): return True if r < 0 or r >= rows or c < 0 or c >= cols: return False if board[r][c] != word[idx]: return False temp = board[r][c] board[r][c] = "#" # Choose (mark visited) found = (backtrack(r+1, c, idx+1) or backtrack(r-1, c, idx+1) or backtrack(r, c+1, idx+1) or backtrack(r, c-1, idx+1)) # Explore board[r][c] = temp # Unchoose (restore) return found for r in range(rows): for c in range(cols): if backtrack(r, c, 0): return True return False

Permutations Step-by-Step Trace

backtrack(path=[], used=[F,F,F]) Choose 1 -> backtrack(path=[1], used=[T,F,F]) Choose 2 -> backtrack(path=[1,2], used=[T,T,F]) Choose 3 -> path=[1,2,3] SOLUTION! -> unchoose 3 Unchoose 2 Choose 3 -> backtrack(path=[1,3], used=[T,F,T]) Choose 2 -> path=[1,3,2] SOLUTION! -> unchoose 2 Unchoose 3 Unchoose 1 Choose 2 -> ... (continues for all 6 permutations)

N-Queens (n=4) Output

Solution 1: Solution 2: . Q . . . . Q . . . . Q Q . . . Q . . . . . . Q . . Q . . Q . .

Pruning Strategies

Optimization
  • Sort the input: Sorting helps skip duplicates and enables early termination (e.g., if current sum exceeds target, stop).
  • Constraint propagation: In N-Queens, tracking columns and diagonals in sets gives O(1) conflict checks.
  • Skip duplicates: For problems with duplicate elements, sort first and skip if i > start and nums[i] == nums[i-1].
  • Bound checking: If remaining elements cannot possibly complete a valid solution, prune early.

Backtracking vs DFS vs DP

Aspect Backtracking DFS Dynamic Programming
Goal Find all (or one) valid solutions Traverse/search a graph Find optimal value
Pruning Yes, key feature Rarely N/A (memoization)
Undo step Yes (unchoose) No No
Typical use Permutations, combos, puzzles Graph traversal, cycles Optimization, counting

Deep Dives

Advanced

Deep Dive 1: Pruning Optimization

Effective pruning can reduce exponential time dramatically. For example, N-Queens without pruning explores n^n states; with column + diagonal pruning, it explores roughly n! states -- orders of magnitude fewer.

  • Sort input arrays to enable duplicate skipping and early termination.
  • Use bitmask instead of sets for columns/diagonals in N-Queens for constant-factor speedup.
  • For constraint-heavy problems (Sudoku), apply constraint propagation before backtracking.

Deep Dive 2: Iterative vs Recursive Backtracking

Recursive backtracking is more intuitive but uses O(depth) call stack. Iterative approaches use an explicit stack, avoiding stack overflow for deep recursion. However, iterative backtracking is harder to write and rarely needed in interviews.

Common Mistakes

Mistake #1: Forgetting to Undo the Choice

# WRONG: never pops from path -- accumulates all elements for i in range(start, len(nums)): path.append(nums[i]) backtrack(i + 1, path) # Missing: path.pop() # CORRECT: always undo after recursive call for i in range(start, len(nums)): path.append(nums[i]) backtrack(i + 1, path) path.pop() # Undo!

Mistake #2: Not Handling Duplicates

# WRONG: [1,1,2] generates duplicate subsets def subsets_with_dup(nums): # Without sorting and skipping, [1,1] appears twice # CORRECT: sort first, then skip consecutive duplicates nums.sort() for i in range(start, len(nums)): if i > start and nums[i] == nums[i - 1]: continue # Skip duplicate path.append(nums[i]) backtrack(i + 1, path) path.pop()

Practice Problems

Practice Time!
E

Easy: Letter Combinations of a Phone Number (LeetCode 17)

Given a string of digits 2-9, return all possible letter combinations that the number could represent (like a phone keypad).

Hint

Map each digit to its letters. Backtrack through each digit position, choosing one letter at a time.

M

Medium: Palindrome Partitioning (LeetCode 131)

Given a string, partition it so that every substring is a palindrome. Return all possible partitions.

Hint

At each position, try all substrings starting there. If a substring is a palindrome, choose it and recurse on the remainder.

H

Hard: Sudoku Solver (LeetCode 37)

Fill a 9x9 Sudoku board so each row, column, and 3x3 box contains digits 1-9.

Hint

Find the next empty cell. Try digits 1-9, checking row/col/box constraints. Backtrack if no digit works.

Quick Reference Guide

Key Takeaways

  • Choose, Explore, Unchoose -- the universal backtracking template solves most problems.
  • Pruning is critical -- sorting input and checking constraints early cuts branches dramatically.
  • Permutations use a used array; combinations/subsets use a start index to avoid reuse.

Related Topics

Time Complexities

  • Permutations: O(n! * n)
  • Combinations: O(C(n,k) * k)
  • Subsets: O(2^n * n)
  • N-Queens: O(n!)