Backtracking is a problem-solving technique that tries partial solutions and abandons them when they fail. This guide covers the backtracking pattern and classic problems.
Understanding Backtracking
The Concept
┌─────────────────────────────────────────────────────────────┐
│ Backtracking Process │
│ │
│ Problem: Find path through maze │
│ │
│ Start ──► A ──► B ──► C (dead end) │
│ │ │
│ └──► D ──► E (success!) │
│ │
│ Steps: │
│ 1. Try a path │
│ 2. If dead end, backtrack │
│ 3. Try different path │
│ 4. Repeat until solution or all paths tried │
│ │
└─────────────────────────────────────────────────────────────┘
Backtracking Template
def backtrack(candidate, input_data):
# Check if candidate is a valid solution
if is_solution(candidate, input_data):
record_solution(candidate)
return
# Try each possible next choice
for next_choice in generate_choices(candidate, input_data):
# Make the choice
if is_valid(next_choice, candidate, input_data):
make_choice(next_choice, candidate)
# Recurse
backtrack(candidate, input_data)
# Undo the choice (backtrack)
undo_choice(next_choice, candidate)
Classic Problems
N-Queens
def solve_n_queens(n):
"""Place n queens on n×n board without attacks"""
result = []
def is_safe(board, row, col):
# Check column
for i in range(row):
if board[i][col] == 'Q':
return False
# Check diagonals
for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)):
if board[i][j] == 'Q':
return False
for i, j in zip(range(row-1, -1, -1), range(col+1, n)):
if board[i][j] == 'Q':
return False
return True
def solve(board, row):
if row == n:
result.append([''.join(row) for row in board])
return
for col in range(n):
if is_safe(board, row, col):
board[row][col] = 'Q'
solve(board, row + 1)
board[row][col] = '.'
board = [['.' for _ in range(n)] for _ in range(n)]
solve(board, 0)
return result
# Example usage
solutions = solve_n_queens(4)
for sol in solutions:
for row in sol:
print(row)
print()
Permutations
def permute(nums):
"""Generate all permutations"""
result = []
def backtrack(start):
if start == len(nums):
result.append(nums[:])
return
for i in range(start, len(nums)):
# Swap
nums[start], nums[i] = nums[i], nums[start]
# Recurse
backtrack(start + 1)
# Backtrack
nums[start], nums[i] = nums[i], nums[start]
backtrack(0)
return result
# With backtracking template
def permute_template(nums):
result = []
def generate(candidate):
if len(candidate) == len(nums):
result.append(candidate[:])
return
for num in nums:
if num not in candidate:
candidate.append(num)
generate(candidate)
candidate.pop()
generate([])
return result
Subsets
def subsets(nums):
"""Generate all subsets"""
result = []
def generate(index, current):
if index == len(nums):
result.append(current[:])
return
# Include nums[index]
current.append(nums[index])
generate(index + 1, current)
# Exclude nums[index]
current.pop()
generate(index + 1, current)
generate(0, [])
return result
def subsets_with_duplicates(nums):
"""Generate subsets handling duplicates"""
nums.sort()
result = []
def generate(index, current):
result.append(current[:])
for i in range(index, len(nums)):
if i > index and nums[i] == nums[i-1]:
continue
current.append(nums[i])
generate(i + 1, current)
current.pop()
generate(0, [])
return result
Combination Sum
def combination_sum(candidates, target):
"""Find combinations that sum to target"""
result = []
candidates.sort() # For early termination
def backtrack(start, target, current):
if target == 0:
result.append(current[:])
return
if target < 0:
return
for i in range(start, len(candidates)):
current.append(candidates[i])
backtrack(i, target - candidates[i], current)
current.pop()
backtrack(0, target, [])
return result
def combination_sum_ii(candidates, target):
"""Each number can be used once"""
candidates.sort()
result = []
def backtrack(index, target, current):
if target == 0:
result.append(current[:])
return
if target < 0:
return
for i in range(index, len(candidates)):
if i > index and candidates[i] == candidates[i-1]:
continue
current.append(candidates[i])
backtrack(i + 1, target - candidates[i], current)
current.pop()
backtrack(0, target, [])
return result
Sudoku Solver
def solve_sudoku(board):
"""Solve Sudoku puzzle"""
def is_valid(board, row, col, num):
# Check row
if num in board[row]:
return False
# Check column
for i in range(9):
if board[i][col] == num:
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 solve():
for i in range(9):
for j in range(9):
if board[i][j] == '.':
for num in '123456789':
if is_valid(board, i, j, num):
board[i][j] = num
if solve():
return True
board[i][j] = '.'
return False
return True
solve()
return board
# Example board
board = [
['5', '3', '.', '.', '7', '.', '.', '.', '.'],
['6', '.', '.', '1', '9', '5', '.', '.', '.'],
['.', '9', '8', '.', '.', '.', '.', '6', '.'],
['8', '.', '.', '.', '6', '.', '.', '.', '3'],
['4', '.', '.', '8', '.', '3', '.', '.', '1'],
['7', '.', '.', '.', '2', '.', '.', '.', '6'],
['.', '6', '.', '.', '.', '.', '2', '8', '.'],
['.', '.', '.', '4', '1', '9', '.', '.', '5'],
['.', '.', '.', '.', '8', '.', '.', '7', '9']
]
solve_sudoku(board)
for row in board:
print(row)
Word Search
def exist(board, word):
"""Find if word exists in board"""
if not board or not board[0]:
return False
rows, cols = len(board), len(board[0])
def dfs(r, c, index):
if index == len(word):
return True
if (r < 0 or c < 0 or r >= rows or c >= cols or
board[r][c] != word[index]):
return False
# Mark as visited
temp = board[r][c]
board[r][c] = '#'
# Explore neighbors
found = (dfs(r+1, c, index+1) or
dfs(r-1, c, index+1) or
dfs(r, c+1, index+1) or
dfs(r, c-1, index+1))
# Backtrack
board[r][c] = temp
return found
for i in range(rows):
for j in range(cols):
if dfs(i, j, 0):
return True
return False
def find_words(board, words):
"""Find all words from list in board"""
result = set()
def build_trie(words):
trie = {}
for word in words:
node = trie
for char in word:
node = node.setdefault(char, {})
node['$'] = word
return trie
trie = build_trie(words)
def dfs(r, c, node):
if '$' in node:
result.add(node['$'])
if r < 0 or c < 0 or r >= len(board) or c >= len(board[0]):
return
char = board[r][c]
if char not in node:
return
# Mark as visited
board[r][c] = '#'
dfs(r+1, c, node[char])
dfs(r-1, c, node[char])
dfs(r, c+1, node[char])
dfs(r, c-1, node[char])
# Backtrack
board[r][c] = char
for i in range(len(board)):
for j in range(len(board[0])):
dfs(i, j, trie)
return list(result)
Time Complexity Analysis
# Backtracking complexity
complexity_analysis = {
"permutations": {
"time": "O(n! × n)",
"space": "O(n)"
},
"subsets": {
"time": "O(2^n × n)",
"space": "O(n)"
},
"n_queens": {
"time": "O(n!)",
"space": "O(n)"
},
"sudoku": {
"time": "O(9^(n×n)) worst",
"space": "O(n×n)"
}
}
Conclusion
Backtracking solves complex constraint problems:
- Pattern: Try, recurse, backtrack
- N-Queens: Place n queens safely
- Permutations/Subset: Generate all possibilities
- Sudoku: Constraint satisfaction
Key: Prune invalid branches early for efficiency.
Comments