Recursion and Backtracking Interview Patterns
Backtracking is systematic exhaustive search with pruning. It builds candidates incrementally and abandons (backtracks) as soon as it determines a candidate cannot lead to a valid solution. Essential for permutations, combinations, constraint satisfaction, and maze/grid problems.
Backtracking Template
def backtrack(state, choices, result):
# Base case: state is a valid complete solution
if is_complete(state):
result.append(state[:]) # copy current state
return
for choice in choices:
if is_valid(state, choice):
# Make choice
state.append(choice)
# Recurse
backtrack(state, remaining_choices(choices, choice), result)
# Undo choice (backtrack)
state.pop()
Pattern 1: Permutations
def permutations(nums):
result = []
def backtrack(current, remaining):
if not remaining:
result.append(current[:])
return
for i in range(len(remaining)):
current.append(remaining[i])
backtrack(current, remaining[:i] + remaining[i+1:])
current.pop()
backtrack([], nums)
return result
# Permutations with duplicates (sort + skip)
def perms_unique(nums):
nums.sort()
result = []
used = [False] * len(nums)
def backtrack(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
used[i] = True
current.append(nums[i])
backtrack(current)
current.pop()
used[i] = False
backtrack([])
return result
Pattern 2: Combinations and Subsets
# All subsets (power set)
def subsets(nums):
result = []
def backtrack(start, current):
result.append(current[:]) # add current state at every node
for i in range(start, len(nums)):
current.append(nums[i])
backtrack(i + 1, current)
current.pop()
backtrack(0, [])
return result
# Combinations of size k
def combine(n, k):
result = []
def backtrack(start, current):
if len(current) == k:
result.append(current[:])
return
for i in range(start, n + 1):
current.append(i)
backtrack(i + 1, current)
current.pop()
backtrack(1, [])
return result
# Combination sum (elements can repeat, target sum)
def combination_sum(candidates, target):
candidates.sort()
result = []
def backtrack(start, current, remaining):
if remaining == 0:
result.append(current[:])
return
for i in range(start, len(candidates)):
if candidates[i] > remaining: break # pruning
current.append(candidates[i])
backtrack(i, current, remaining - candidates[i]) # i (not i+1) allows reuse
current.pop()
backtrack(0, [], target)
return result
Pattern 3: N-Queens
Place N queens so none attack each other. Track column and diagonal occupancy:
def solve_n_queens(n):
result = []
cols = set()
diag1 = set() # (row - col) constant on diagonal
diag2 = set() # (row + col) constant on / diagonal
def backtrack(row, board):
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
cols.add(col); diag1.add(row-col); diag2.add(row+col)
board[row][col] = 'Q'
backtrack(row + 1, board)
cols.remove(col); diag1.remove(row-col); diag2.remove(row+col)
board[row][col] = '.'
board = [['.']*n for _ in range(n)]
backtrack(0, board)
return result
Pattern 4: Word Search on Grid
def word_search(board, word):
rows, cols = len(board), len(board[0])
def dfs(r, c, i):
if i == len(word): return True
if r = rows or c = cols: return False
if board[r][c] != word[i]: return False
temp = board[r][c]
board[r][c] = '#' # mark visited
found = any(dfs(r+dr, c+dc, i+1) for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)])
board[r][c] = temp # restore
return found
return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))
Pattern 5: Sudoku Solver
def solve_sudoku(board):
def is_valid(board, row, col, num):
box_r, box_c = 3 * (row // 3), 3 * (col // 3)
return (
num not in board[row] and
num not in [board[r][col] for r in range(9)] and
num not in [board[box_r+r][box_c+c] for r in range(3) for c in range(3)]
)
def backtrack():
for r in range(9):
for c in range(9):
if board[r][c] == '.':
for num in '123456789':
if is_valid(board, r, c, num):
board[r][c] = num
if backtrack(): return True
board[r][c] = '.'
return False # no valid number found
return True # all cells filled
backtrack()
Classic Backtracking Problems
| Problem | State | Branching Factor | Pruning |
|---|---|---|---|
| Permutations | Current sequence | n-k remaining | Skip used elements |
| Subsets | Current subset | n-i remaining | None (collect all) |
| Combination Sum | Current sum | Candidates ≤ remaining | Sort + break early |
| N-Queens | Row placement | n columns | Col/diagonal sets |
| Word Search | Grid position | 4 directions | Bounds + visited |
| Sudoku Solver | Board state | 9 digits | Row/col/box constraints |
| Palindrome Partition | Current partition | Remaining suffixes | Only palindrome splits |
Interview Tips
- Always draw the decision tree for 2-3 levels before coding
- The three steps: make a choice, recurse, undo the choice (backtrack)
- Pruning is the key to performance — identify invalid states early
- For permutations with duplicates: sort first, skip nums[i] == nums[i-1] when nums[i-1] not used
- Time complexity: O(branching_factor^depth) in the worst case, much better with pruning
🏢 Asked at: Uber Interview Guide 2026: Dispatch Systems, Geospatial Algorithms, and Marketplace Engineering