28 questions using this pattern
Build solutions incrementally, exploring choices one at a time and abandoning paths that fail to satisfy constraints. Backtracking systematically explores all possibilities by making a choice, recursing, then undoing the choice.
Imagine navigating a maze by always trying the left path first. When you hit a dead end, you backtrack to the last intersection and try the next option. You systematically explore every possible route, backing up whenever you reach an invalid state.
Another analogy: filling out a Sudoku puzzle. You try a number in an empty cell. If it leads to a contradiction later, you erase it (backtrack) and try the next number. If no number works, you backtrack further to a previous cell.
Backtracking is a refined brute force that prunes invalid branches early. The pattern follows a template:
The key insight is that we build a decision tree where each node represents a state and edges represent choices. Backtracking is a DFS of this tree, with pruning of subtrees that can't lead to valid solutions.
Pruning is what makes backtracking efficient. By detecting invalid states early, we avoid exploring exponentially many useless branches.
def subsets(nums: list[int]) -> list[list[int]]: result = [] def backtrack(start: int, current: list[int]): # Add current subset to result result.append(current[:]) # Try including each remaining element for i in range(start, len(nums)): current.append(nums[i]) # Choose backtrack(i + 1, current) # Explore current.pop() # Unchoose backtrack(0, []) return resultGiven nums = [1, 2, 3], find all possible subsets. A subset can include any combination of elements, including the empty set.
Generating subsets of [1, 2, 3]:
Decision tree (include or exclude each element):
[]
/ \
[1] []
/ \ / \
[1,2] [1] [2] []
/ \ / \ / \ / \
[1,2,3][1,2][1,3][1][2,3][2][3][]
Subsets: [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]
N-Queens (N=4) with pruning:
Place queens row by row, checking column and diagonal conflicts:
Row 0: Try col 0
Row 1: col 0 ❌ (same col)
col 1 ❌ (diagonal)
col 2 ✓
Row 2: col 0 ❌ (diagonal)
col 1 ❌ (col 1 attacks via diagonal)
col 2 ❌ (same col)
col 3 ❌ (diagonal)
Backtrack!
Row 1: col 3 ✓
Row 2: col 1 ✓
Row 3: col 0 ❌
col 1 ❌
col 2 ❌
col 3 ❌
Backtrack!
...
Eventually find: [1, 3, 0, 2] (queens at cols 1,3,0,2 for rows 0,1,2,3)
Template visualization:
backtrack(state):
if is_solution(state):
record_solution(state)
return
for choice in get_choices(state):
if is_valid(choice, state): ← PRUNE
make_choice(choice, state) ← CHOOSE
backtrack(state) ← EXPLORE
undo_choice(choice, state) ← UNCHOOSE
Use this skeleton as a starting point for problems using this pattern:
def generate_subsets(nums: list[int]) -> list[list[int]]:
"""Generate all subsets (power set)."""
result = []
def backtrack(start: int, path: list[int]):
result.append(path[:]) # Record current subset
for i in range(start, len(nums)):
path.append(nums[i]) # Choose
backtrack(i + 1, path) # Explore
path.pop() # Unchoose
backtrack(0, [])
return result
def generate_permutations(nums: list[int]) -> list[list[int]]:
"""Generate all permutations."""
result = []
used = [False] * len(nums)
def backtrack(path: list[int]):
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
used[i] = True # Choose
path.append(nums[i])
backtrack(path) # Explore
path.pop() # Unchoose
used[i] = False
backtrack([])
return result
def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
"""Find combinations that sum to target (can reuse elements)."""
result = []
def backtrack(start: int, path: list[int], remaining: int):
if remaining == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
if candidates[i] > remaining: # Prune
continue
path.append(candidates[i])
backtrack(i, path, remaining - candidates[i]) # Can reuse
path.pop()
candidates.sort() # Enable pruning
backtrack(0, [], target)
return result
def solve_n_queens(n: int) -> list[list[str]]:
"""Find all valid N-Queens solutions."""
result = []
cols = set()
diag1 = set() # row - col
diag2 = set() # row + col
def backtrack(row: int, queens: list[int]):
if row == n:
# Convert to board representation
board = []
for c in 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: under attack
# Choose
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
queens.append(col)
backtrack(row + 1, queens) # Explore
# Unchoose
queens.pop()
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
backtrack(0, [])
return result
def word_search(board: list[list[str]], word: str) -> bool:
"""Check if word exists in grid following adjacent cells."""
rows, cols = len(board), len(board[0])
def backtrack(r: int, c: int, i: int) -> bool:
if i == len(word):
return True
if (r < 0 or r >= rows or c < 0 or c >= cols
or board[r][c] != word[i]):
return False
# Choose: mark as visited
temp = board[r][c]
board[r][c] = '#'
# Explore neighbors
found = (backtrack(r + 1, c, i + 1) or
backtrack(r - 1, c, i + 1) or
backtrack(r, c + 1, i + 1) or
backtrack(r, c - 1, i + 1))
# Unchoose: restore
board[r][c] = temp
return found
for r in range(rows):
for c in range(cols):
if backtrack(r, c, 0):
return True
return FalseLook for these keywords and patterns in problem descriptions:
Not undoing the choice after exploring leaves state modified, causing incorrect results for subsequent branches.
Fix:
Always pair choose with unchoose:
path.append(choice) # Choose
backtrack(...) # Explore
path.pop() # Unchoose - MUST DO!
Adding the same path object to results multiple times—they all reference the same list that keeps changing.
Fix:
Copy the path when recording:
result.append(path[:]) # Shallow copy
# or
result.append(list(path))
Generate all subsets. Each element is either included or not. Record at every node, not just leaves.
Examples: Subsets, Subsets II (with duplicates)
Generate all orderings. Track which elements are used. Record only at leaves (when all elements used).
Examples: Permutations, Permutations II
Generate subsets of specific size k, or combinations that meet a target sum. Use start index to avoid duplicates.
Examples: Combinations, Combination Sum
Place elements satisfying constraints (non-attacking queens, valid Sudoku). Heavy pruning based on constraints.
Examples: N-Queens, Sudoku Solver
Find paths in grids or graphs, marking visited cells temporarily. Unmark when backtracking.
Examples: Word Search, Unique Paths III
Start here to build foundational understanding.
Master the pattern with these representative problems.
Test your mastery with complex variations.
Explore similar techniques:
Break problems into overlapping subproblems, storing results to avoid recomputation. This transforms exponential time complexity into polynomial by trading space for time.
Explore as deep as possible along each branch before backtracking, using recursion or an explicit stack. DFS is memory-efficient and naturally suited for problems involving paths, connectivity, and exhaustive exploration.
Checking validity only at leaf nodes means exploring many invalid branches that could have been cut early.
Fix:
Validate as early as possible:
for choice in choices:
if is_valid(choice): # Prune BEFORE recursing
make_choice(choice)
backtrack(...)
Recording partial solutions as complete, or not recognizing when a complete solution is reached.
Fix:
Clearly define what constitutes a complete solution: