Recursion and backtracking
Backtracking explores a decision tree, undoing choices that lead to dead ends. The skeleton is always: pick → recurse → unpick. Used for permutations, subsets, combinations, constraint problems (N-queens, sudoku, word search).
Template
def backtrack(state, choices):
if is_solution(state):
record(state)
return
for choice in choices:
if not valid(choice, state):
continue
apply(choice, state) # pick
backtrack(state, next_choices)
undo(choice, state) # unpick (the "back" in backtrack)The undo step is what distinguishes backtracking from plain recursion.
Subsets (power set)
def subsets(nums):
result = []
def go(start, current):
result.append(current[:]) # snapshot
for i in range(start, len(nums)):
current.append(nums[i])
go(i + 1, current)
current.pop()
go(0, [])
return resultEach level chooses whether to include each remaining element. current[:] snapshots — without the copy, all entries would be aliased to the same list.
For unique-input subsets: sort, then skip duplicates at each level:
def subsets_with_dup(nums):
nums.sort()
result = []
def go(start, current):
result.append(current[:])
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i-1]:
continue # skip dup at same level
current.append(nums[i])
go(i + 1, current)
current.pop()
go(0, [])
return resultPermutations
def permutations(nums):
result = []
def go(current, remaining):
if not remaining:
result.append(current[:])
return
for i in range(len(remaining)):
current.append(remaining[i])
go(current, remaining[:i] + remaining[i+1:])
current.pop()
go([], nums)
return resultOr with a used set:
def permutations_used(nums):
result = []
used = [False] * len(nums)
def go(current):
if len(current) == len(nums):
result.append(current[:])
return
for i in range(len(nums)):
if used[i]: continue
used[i] = True
current.append(nums[i])
go(current)
current.pop()
used[i] = False
go([])
return resultFor unique permutations of a list with duplicates, sort and skip:
def permutations_unique(nums):
nums.sort()
result = []
used = [False] * len(nums)
def go(current):
if len(current) == len(nums):
result.append(current[:])
return
for i in range(len(nums)):
if used[i]: continue
if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
continue # skip dup unless its predecessor is in use
used[i] = True
current.append(nums[i])
go(current)
current.pop()
used[i] = False
go([])
return resultThe not used[i-1] check ensures duplicates appear in a fixed order.
Combinations
itertools.combinations covers most cases:
from itertools import combinations
list(combinations([1, 2, 3, 4], 2)) # [(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)]Manual version:
def combinations_manual(nums, k):
result = []
def go(start, current):
if len(current) == k:
result.append(current[:])
return
for i in range(start, len(nums)):
current.append(nums[i])
go(i + 1, current)
current.pop()
go(0, [])
return resultN-queens
Place N queens on N×N board so none attack each other.
def solve_n_queens(n):
result = []
cols = set()
diag1 = set() # r - c
diag2 = set() # r + c
placement = [-1] * n
def go(row):
if row == n:
result.append([
"." * c + "Q" + "." * (n - c - 1)
for c in placement
])
return
for col in range(n):
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue
cols.add(col); diag1.add(row - col); diag2.add(row + col)
placement[row] = col
go(row + 1)
cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)
go(0)
return resultThree sets track which columns and diagonals are under attack — O(1) lookups instead of scanning the board.
Word search (grid + backtracking)
def word_search(board, word):
rows, cols = len(board), len(board[0])
def go(r, c, idx):
if idx == len(word): return True
if not (0 <= r < rows and 0 <= c < cols): return False
if board[r][c] != word[idx]: return False
# Mark visited
original, board[r][c] = board[r][c], "#"
found = (
go(r+1, c, idx+1) or go(r-1, c, idx+1) or
go(r, c+1, idx+1) or go(r, c-1, idx+1)
)
# Unmark
board[r][c] = original
return found
for r in range(rows):
for c in range(cols):
if go(r, c, 0):
return True
return FalseMutating the board to mark visited cells avoids needing a separate visited set. The unmarking step is the “back” in backtrack.
Pattern: recursion vs iteration
For trees and recursive structures, recursion is natural. For tight loops or deep nesting risking stack overflow, iterate with an explicit stack.
Python’s default recursion limit is 1000 — sys.setrecursionlimit(10_000) to bump, but it’s a sign you should iterate instead.
Pitfalls
- Forgetting to undo — state leaks between branches.
- Storing references instead of copies —
result.append(current)instead ofresult.append(current[:])causes all entries to alias. - Missing pruning — without
if not valid: continue, you explore the whole tree (exponential). - Wrong recursion limit — Python’s 1000 default trips on N > 1000ish problems.
- Mutating the input without restoring it — caller may not expect side effects.
Interview angle
- “What is backtracking?” - DFS over a decision tree where you undo each choice after exploring it. The template is choose, recurse, un-choose, with a pruning check that abandons branches which cannot lead to a valid solution.
- “What makes it faster than brute force?” - pruning. N-Queens is
O(n!)-flavoured rather thann^nbecause a conflicting placement kills an entire subtree immediately. Without pruning it’s just exhaustive enumeration. - “How do you handle duplicates?” - sort first, then skip an element equal to its predecessor at the same recursion depth. This is the standard fix for subsets-with-duplicates and permutations-with-duplicates, and it’s easy to state and easy to get subtly wrong.
- “Why append a copy of the current path?” - the path list is mutated as you backtrack, so storing a reference means every recorded result ends up identical or empty.
result.append(path[:])is the fix.