■ Universal Backtracking & Recursion Cheat Sheet
1. The 4-Part Backtracking Template
def backtrack(start, path):
# 1. Base case
if end_condition(path):
results.append(path[:])
return
# 2. Explore choices
for choice in choices_from(start):
if is_valid(choice, path): # 3. Prune
path.append(choice) # 4a. Choose
backtrack(next_start(choice), path) # 4b. Explore
path.pop() # 4c. Undo
2. Recognizing Backtracking Problems
Backtracking appears when you need to: - Generate all possibilities - Build solutions step-by-step and discard bad
ones - Make decisions sequentially Common problems: - Combinations, Permutations, Subsets - Constraint
satisfaction (Sudoku, N-Queens) - Path finding in grids - Word search / letter combinations
3. The Three Golden Questions
1. Path: What represents a partial solution? 2. Choices: What options can I pick at each step? 3. End Condition:
When do I know the solution is complete?
4. Backtracking Patterns with Examples
### Pattern 1: Subsets
def subsets(nums):
res = []
def backtrack(start, path):
res.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i+1, path)
path.pop()
backtrack(0, [])
return res
### Pattern 2: Combinations (fixed size)
def combine(n, k):
res = []
def backtrack(start, path):
if len(path) == k:
res.append(path[:])
return
for i in range(start, n+1):
path.append(i)
backtrack(i+1, path)
path.pop()
backtrack(1, [])
return res
### Pattern 3: Permutations
def permute(nums):
res = []
used = [False]*len(nums)
def backtrack(path):
if len(path) == len(nums):
res.append(path[:])
return
for i in range(len(nums)):
if not used[i]:
used[i] = True
path.append(nums[i])
backtrack(path)
path.pop()
used[i] = False
backtrack([])
return res
### Pattern 4: Combination Sum
def combinationSum(candidates, target):
res = []
def backtrack(start, path, total):
if total == target:
res.append(path[:])
return
if total > target:
return
for i in range(start, len(candidates)):
path.append(candidates[i])
backtrack(i, path, total + candidates[i])
path.pop()
backtrack(0, [], 0)
return res
### Pattern 5: N-Queens
def solveNQueens(n):
res = []
cols, diag1, diag2 = set(), set(), set()
board = [["."]*n for _ in range(n)]
def backtrack(r):
if r == n:
res.append(["".join(row) for row in board])
return
for c in range(n):
if c in cols or (r-c) in diag1 or (r+c) in diag2:
continue
cols.add(c); diag1.add(r-c); diag2.add(r+c)
board[r][c] = "Q"
backtrack(r+1)
board[r][c] = "."
cols.remove(c); diag1.remove(r-c); diag2.remove(r+c)
backtrack(0)
return res
### Pattern 6: Word Search
def exist(board, word):
rows, cols = len(board), len(board[0])
path = set()
def backtrack(r, c, i):
if i == len(word):
return True
if (r < 0 or c < 0 or r >= rows or c >= cols or
word[i] != board[r][c] or (r,c) in path):
return False
path.add((r, c))
res = (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))
path.remove((r, c))
return res
for r in range(rows):
for c in range(cols):
if backtrack(r, c, 0):
return True
return False
5. Common Mistakes
- Forgetting path.pop() (state pollution) - Not pruning early - Modifying path without copying (need path[:]) - Using
recursion without a clear base case
6. Thinking in a Recursion Tree
- Each level = decision step - Each branch = a choice - DFS explores one branch fully before backtracking -
Backtracking = moving up to try another branch
7. Time Complexity Intuition
- Subsets: O(2^n) - Permutations: O(n!) - Combinations: O(C(n, k)) - Sudoku / N-Queens: Exponential but pruned
heavily
8. Mini Mind Map
Recursion
■■■ Pure Recursion (divide into subproblems)
■■■ Backtracking
■■■ Generate & Check
■■■ Undo on return
■■■ Prune early
