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
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What is the backtracking template and how does it differ from DFS?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Backtracking is DFS with the additional step of undoing a choice (backtracking) after exploring that branch. The template: (1) base case — if state is complete, record solution; (2) for each valid choice, make the choice, recurse, then undo the choice. DFS typically visits nodes without undoing; backtracking explicitly restores state. The critical difference is the "undo" step, which allows reusing the same mutable state object across all branches without creating copies.” }
},
{
“@type”: “Question”,
“name”: “How do you generate all permutations of a list with duplicate elements?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Sort the array first. Use a boolean "used" array to track which elements are in the current permutation. For each position, skip element i if: (1) used[i] is true, or (2) nums[i] == nums[i-1] and used[i-1] is false. Condition 2 prevents generating the same permutation by choosing identical elements in different orders. This is the canonical pattern for all "with duplicates" backtracking problems (subsets II, combination sum II).” }
},
{
“@type”: “Question”,
“name”: “How do you solve the N-Queens problem efficiently?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Place one queen per row. Track three sets: occupied columns (cols), occupied main diagonals (row-col is constant), and occupied anti-diagonals (row+col is constant). For each row, try all columns that don't conflict with any set. When all N rows are placed, record the solution. Using sets gives O(1) conflict checking versus O(n) array scanning. Total time O(n!) in the worst case, but the pruning typically reduces it dramatically—N=8 has only 92 solutions out of 8^8 = 16M possibilities.” }
}
]
}