Backtracking: Pruning the Search Tree for Permutations, N-Queens and Sudoku
Key takeaways
Backtracking is depth-first search over a tree of partial solutions that abandons a branch as soon as it can no longer lead to an answer. The template is short; what decides performance is how early you prune and in what order you try choices.
Introduction
Backtracking explores all possibilities but immediately abandons when conditions are not met.
A useful way to picture it is as a tree. The root is the empty state, each edge is one choice (“put a queen in column 3”, “take element 2”), and each leaf is a complete candidate. Brute force builds every leaf and checks it at the end. Backtracking checks at every node on the way down. When a partial state is already invalid, it drops the entire subtree below that node. For 8-Queens, brute force over one queen per row means 8⁸ ≈ 16.7 million leaves. A backtracking solver that checks columns and diagonals after each placement visits only about 2,000 nodes to find all 92 solutions.
That is the key point of this article: the recursive template is almost always the same, and the complexity bounds in textbooks (O(n!), O(2ⁿ)) are almost always the same. What separates a solution that runs in 10 ms from one that times out is how early a dead branch is detected and in what order choices are tried. Most of the prose below is about those two decisions.
Backtracking Basics
DFS vs Backtracking
DFS follows connected structures to the end while visiting, and backtracking undoes choices when they don’t satisfy conditions and tries other branches. Like erasing footsteps and returning to previous forks when reaching a dead end in a maze.
# DFS: Visit all nodes
def dfs(node):
visit(node)
for child in node.children:
dfs(child)
# Backtracking: Check conditions + pruning
def backtrack(state):
if is_solution(state):
add_solution(state)
return
for choice in get_choices(state):
if is_valid(choice): # Pruning!
make_choice(choice)
backtrack(state)
undo_choice(choice) # UndoBacktracking Template
def backtrack(state, choices):
# 1. Base case (solution found)
if is_complete(state):
save_solution(state)
return
# 2. Pruning (important!)
if not is_valid(state):
return
# 3. Try choices
for choice in choices:
# Make choice
state.add(choice)
# Recurse
backtrack(state, new_choices)
# Undo choice
state.remove(choice)Why undo instead of copying? You could pass a fresh copy of the state into each recursive call and skip the undo step entirely. It is simpler and harder to get wrong. The cost is that every node in the search tree then allocates a new state. With a depth of 10 and a state of 10 elements, that is 10 element copies per call, and the number of calls is exponential. Mutating one shared state and undoing it on the way back keeps memory at O(depth) and removes the allocation cost. The trade-off is correctness: every mutation must have an exactly matching undo on every return path, including early returns. Most backtracking bugs are an undo that does not match its mutation.
Immutable values are the exception. When the state is a string or an integer (as in the parentheses example below), path + '(' already creates a new value, so there is nothing to undo.
Permutations and Combinations
Permutation
Order matters, no duplicates:
def permutations(arr, n):
"""
Select n from arr (order matters)
[1,2,3], n=2 → [[1,2], [1,3], [2,1], [2,3], [3,1], [3,2]]
"""
result = []
def backtrack(path, remaining):
if len(path) == n:
result.append(path[:])
return
for i in range(len(remaining)):
path.append(remaining[i])
backtrack(path, remaining[:i] + remaining[i+1:])
path.pop()
backtrack([], arr)
return result
# Test
print(permutations([1, 2, 3], 2))
# [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]Using Visited Array:
def permutations_visited(arr, n):
"""
Permutations using visited array (more efficient)
"""
result = []
visited = [False] * len(arr)
def backtrack(path):
if len(path) == n:
result.append(path[:])
return
for i in range(len(arr)):
if not visited[i]:
visited[i] = True
path.append(arr[i])
backtrack(path)
path.pop()
visited[i] = False
backtrack([])
return resultThe first version is easier to read, but remaining[:i] + remaining[i+1:] builds a new list at every node, which costs O(n) time and memory per call. The visited version checks a boolean and flips it back, so it does O(1) bookkeeping per choice. For n = 8 that does not matter. For n = 10 (3.6 million permutations) the slicing version is noticeably slower, and in Python the extra allocation also puts pressure on the garbage collector.
If the input can contain duplicates (LeetCode 47), both versions produce repeated permutations. The standard fix is to sort the input first, then skip arr[i] when arr[i] == arr[i-1] and arr[i-1] is not currently used. That forces equal values to be placed in one fixed order, so each distinct arrangement appears exactly once. Deduplicating the results with a set afterwards also gives correct output, but it still explores every duplicate subtree, so you pay the full n! cost.
Combination
Combinations ignore order and only care about what was selected. {1,2} and {2,1} are the same combination.
def combinations(arr, n):
"""
Select n from arr (order doesn't matter)
[1,2,3], n=2 → [[1,2], [1,3], [2,3]]
"""
result = []
def backtrack(start, path):
if len(path) == n:
result.append(path[:])
return
for i in range(start, len(arr)):
path.append(arr[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
# Test
print(combinations([1, 2, 3], 2))
# [[1, 2], [1, 3], [2, 3]]The start index is what turns permutations into combinations. Because the next choice may only come from positions after the current one, [2, 1] can never be built once [1, 2] exists. There is also a cheap extra prune: if len(path) + (len(arr) - i) < n, there are not enough elements left to finish the combination, so the loop can stop early. For “choose 3 of 30” that removes a large number of branches that could never reach length 3.
Permutation vs Combination:
arr = [1, 2, 3], n=2
Permutation (order matters):
[1,2], [1,3], [2,1], [2,3], [3,1], [3,2]
Total: 6 (3P2 = 3!/(3-2)! = 6)
Combination (order doesn't matter):
[1,2], [1,3], [2,3]
Total: 3 (3C2 = 3!/(2!*1!) = 3)N-Queen Problem
Problem
Place N queens on N×N chessboard (no attacks):
def solve_n_queens(n):
"""
N-Queen problem
"""
result = []
board = [['.'] * n for _ in range(n)]
def is_valid(row, col):
# Check same column
for i in range(row):
if board[i][col] == 'Q':
return False
# Check left diagonal
i, j = row - 1, col - 1
while i >= 0 and j >= 0:
if board[i][j] == 'Q':
return False
i -= 1
j -= 1
# Check right diagonal
i, j = row - 1, col + 1
while i >= 0 and j < n:
if board[i][j] == 'Q':
return False
i -= 1
j += 1
return True
def backtrack(row):
if row == n:
result.append([''.join(r) for r in board])
return
for col in range(n):
if is_valid(row, col):
board[row][col] = 'Q'
backtrack(row + 1)
board[row][col] = '.' # Undo
backtrack(0)
return result
# Test
solutions = solve_n_queens(4)
print(f"{len(solutions)} solutions")
for sol in solutions:
for row in sol:
print(row)
print()Optimized with Sets:
def solve_n_queens_optimized(n):
"""
N-Queen with O(1) validation using sets
"""
result = []
board = [['.'] * n for _ in range(n)]
cols = set()
diag1 = set() # row - col
diag2 = set() # row + col
def backtrack(row):
if row == n:
result.append([''.join(r) for r in board])
return
for col in range(n):
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue
# Make choice
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
board[row][col] = 'Q'
backtrack(row + 1)
# Undo choice
board[row][col] = '.'
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
backtrack(0)
return resultTwo design choices make N-Queens tractable. First, placing one queen per row means the row constraint is enforced by the structure of the recursion, so it never needs to be checked. The search space drops from C(64, 8) ≈ 4.4 billion placements to 8⁸ before any pruning. Second, the set version replaces an O(n) scan of the board with three O(1) lookups. All squares on the same "" diagonal share row - col, and all squares on the same ”/” diagonal share row + col, so one integer identifies each diagonal.
For large n, competitive programmers replace the three sets with three bitmasks and compute available columns as ~(cols | d1 | d2) & ((1 << n) - 1). Each placement is then a few bit operations, which is how n = 15 or 16 can be counted in seconds.
Practical Problems
Problem 1: Subset Sum
def subset_sum(arr, target):
"""
Find subsets that sum to target
"""
result = []
def backtrack(start, path, current_sum):
if current_sum == target:
result.append(path[:])
return
if current_sum > target: # Pruning
return
for i in range(start, len(arr)):
path.append(arr[i])
backtrack(i + 1, path, current_sum + arr[i])
path.pop()
backtrack(0, [], 0)
return result
# Test
arr = [1, 2, 3, 4, 5]
target = 5
print(subset_sum(arr, target))
# [[1, 4], [2, 3], [5]]The prune current_sum > target is only correct when every number is non-negative. With negative numbers, a sum that is over the target can still come back down, so this check silently discards valid answers. It will not crash or error. The function just returns fewer results, which is very hard to notice in a test that only uses positive inputs. If the input is non-negative, sort it first. Then, as soon as current_sum + arr[i] > target, you can break out of the loop instead of skipping one element, because every later element is at least as large.
Problem 2: Sudoku Solver
def solve_sudoku(board):
"""
Solve 9x9 sudoku
"""
def is_valid(row, col, num):
# Check row
if num in board[row]:
return False
# Check column
if num in [board[i][col] for i in range(9)]:
return False
# Check 3x3 box
box_row, box_col = 3 * (row // 3), 3 * (col // 3)
for i in range(box_row, box_row + 3):
for j in range(box_col, box_col + 3):
if board[i][j] == num:
return False
return True
def backtrack():
for i in range(9):
for j in range(9):
if board[i][j] == '.':
for num in '123456789':
if is_valid(i, j, num):
board[i][j] = num
if backtrack():
return True
board[i][j] = '.' # Undo
return False
return True
backtrack()
return boardThis solver always fills the first empty cell it finds, scanning row by row. For typical newspaper puzzles that is fast enough. On puzzles designed to defeat naive solvers, it can be very slow, because it may make a wrong guess early in a cell that had 6 options, and the contradiction only shows up dozens of levels deeper.
The standard improvement is the minimum remaining values heuristic: at each step, pick the empty cell with the fewest legal digits. A cell with one candidate costs no branching at all, and a cell with zero candidates fails immediately, which is the earliest possible prune. The cost is that choosing the cell requires computing candidate counts, so keep per-row, per-column, and per-box sets (or bitmasks) instead of rescanning the board inside is_valid, which is O(27) per check in the version above.
When I compare solver versions like this, the first-empty-cell version and the MRV version look the same on easy puzzles, and it is tempting to stop there. The difference shows up only on hard inputs: a well-known “hardest Sudoku” puzzle can take the naive order many seconds in Python, while the MRV version finishes almost instantly. The lesson generalizes beyond Sudoku. Benchmark a backtracking solution on adversarial inputs, not the example from the problem statement, because choice order can change the running time by orders of magnitude while the big-O bound stays the same.
Problem 3: Generate Parentheses
def generate_parentheses(n):
"""
Generate all valid n pairs of parentheses
n=3 → ["((()))", "(()())", "(())()", "()(())", "()()()"]
"""
result = []
def backtrack(path, open_count, close_count):
if len(path) == 2 * n:
result.append(path)
return
# Add '(' if possible
if open_count < n:
backtrack(path + '(', open_count + 1, close_count)
# Add ')' if valid
if close_count < open_count:
backtrack(path + ')', open_count, close_count + 1)
backtrack('', 0, 0)
return result
# Test
print(generate_parentheses(3))
# ['((()))', '(()())', '(())()', '()(())', '()()()']This is a good example of pruning built into choice generation, instead of a separate is_valid check. The code never builds an invalid prefix such as ()), so every leaf it reaches is a valid answer. The number of results grows as the Catalan numbers (1, 2, 5, 14, 42, …), much slower than the 2²ⁿ strings a generate-and-filter approach would test.
Advanced Techniques
Pruning Strategies
# 1. Early termination
if current_sum > target:
return # No point continuing
# 2. Constraint propagation
if remaining_choices < needed:
return # Cannot complete solution
# 3. Symmetry breaking
# Skip symmetric cases to reduce search space
# 4. Memoization
memo = {}
state_key = tuple(sorted(state))
if state_key in memo:
return memo[state_key]Memoization deserves a warning. It only helps when the same subproblem is reached by different paths, and when the answer for that subproblem does not depend on how you got there. “Can the remaining numbers from index i reach sum s?” meets both conditions, and once you memoize on (i, s) you have turned backtracking into dynamic programming (see the next article in the series). N-Queens partial boards, on the other hand, are almost never reached twice. There, a memo dictionary only costs memory. Before adding a memo, ask whether your state key can actually repeat.
Word Search
def word_search(board, word):
"""
Find if word exists in board (can move up/down/left/right)
"""
rows, cols = len(board), len(board[0])
def backtrack(r, c, index):
if index == len(word):
return True
if (r < 0 or r >= rows or c < 0 or c >= cols or
board[r][c] != word[index]):
return False
# Mark as visited
temp = board[r][c]
board[r][c] = '#'
# Try all 4 directions
found = (backtrack(r+1, c, index+1) or
backtrack(r-1, c, index+1) or
backtrack(r, c+1, index+1) or
backtrack(r, c-1, index+1))
# Restore
board[r][c] = temp
return found
for i in range(rows):
for j in range(cols):
if backtrack(i, j, 0):
return True
return False
# Test
board = [
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
print(word_search(board, "ABCCED")) # TrueWord Search marks visited cells by overwriting them with # instead of keeping a separate visited set. This avoids extra memory and a hash lookup per step, but it mutates the caller’s board. The restore line must run on every path, which is why the four recursive calls are combined into one found expression before board[r][c] = temp. If you change the code to return True directly from inside the direction checks, the board is left with # marks, and the next starting cell’s search runs on a corrupted grid. This kind of bug passes the first test case and fails the second, which makes it confusing to debug.
Where Backtracking Solutions Go Wrong
Recursion depth and the call stack
Python’s default recursion limit is 1000. Most backtracking problems stay far below that, because the depth equals the number of choices (8 for 8-Queens, 81 at most for Sudoku). But a flood-fill or path search on a 100×100 grid can reach a depth of 10,000 and fail with RecursionError. Raising the limit with sys.setrecursionlimit works up to a point, beyond which the interpreter itself can crash with a stack overflow. When depth grows with the input size instead of the number of choices, switch to an explicit stack.
This is the failure I run into most often when a solution that passed small tests is run on the full input. It is also a reminder to estimate the maximum depth, not just the number of nodes, before choosing recursion.
Choice order
Try the most constrained choice first (as in the Sudoku MRV heuristic above). When you only need one solution, also try the most promising value first: a good first guess reaches a leaf quickly and ends the search. When you need all solutions, value order does not change the total work, but variable order still does.
Common Mistakes
# ❌ Wrong: Forgot to undo
def backtrack(path):
path.append(choice)
backtrack(path)
# Forgot path.pop()!
# ✅ Correct: Always undo
def backtrack(path):
path.append(choice)
backtrack(path)
path.pop()
# ❌ Wrong: Shallow copy
result.append(path) # path changes later!
# ✅ Correct: Deep copy
result.append(path[:]) # or list(path)The second mistake produces a very recognizable symptom: the result list has the right number of entries, but every entry is an empty list. Each append stored a reference to the same path object, and by the time the search finished, every pop() had emptied it. If you see [[], [], [], []], look for a missing copy.
Estimating whether a backtracking search will finish
| Type | Complexity | Example |
|---|---|---|
| Permutation | O(n!) | All arrangements |
| Combination | O(2ⁿ) | Subset selection |
| N-Queen | O(n!) | Constraint satisfaction |
| Sudoku | O(9^(empty cells)) | Fill grid |
Before writing the recursion, compare the input limit with these growth rates. 10! is about 3.6 million leaves, which Python can enumerate; 12! is about 479 million, which it cannot without heavy pruning. 2²⁰ is about a million subsets, 2³⁰ is about a billion. When the limit sits beyond what raw enumeration allows, the problem is telling you that pruning must cut most branches, or that backtracking is the wrong tool.
The signal for the second case is that different paths reach the same situation. If the rest of the search depends only on something small, such as the current index and the remaining sum, those states repeat, and caching them turns the search into dynamic programming. Backtracking is the right choice when the answer is the list of solutions itself, or when constraints make most branches die early.
Recommended Problems
Baekjoon
LeetCode
- LeetCode 46: Permutations
- LeetCode 47: Permutations II
- LeetCode 77: Combinations
- LeetCode 78: Subsets
- LeetCode 51: N-Queens
- LeetCode 37: Sudoku Solver
- LeetCode 79: Word Search
- LeetCode 22: Generate Parentheses