The short answer
Backtracking is DFS with undo. Ten recurring templates: subsets, permutations, combinations, combination sum, palindrome partitioning, word search on grid, N-Queens, Sudoku solver, phone letter combinations, and restore IP addresses. The common shape is: pick a choice, recurse, unpick. Master the subsets template first; the rest are variations.
Backtracking problems look intimidating and expand to many solutions. The implementation is a short recursive function that picks a choice, recurses, then undoes the choice. Every backtracking problem in interviews is a variation of one of ten templates.
This guide walks each template with a clean Python implementation. Memorize the first three and the rest become obvious.
Pattern 1: Subsets
Given [1,2,3], return all subsets. For each element, choose to include or exclude.
def subsets(nums):
out, path = [], []
def backtrack(i):
if i == len(nums):
out.append(path[:])
return
backtrack(i + 1) # exclude
path.append(nums[i])
backtrack(i + 1) # include
path.pop() # undo
backtrack(0)
return outThe canonical backtracking shape. LeetCode 78.
Pattern 2: Permutations
All orderings. Track which elements are used; try each unused one at each position.
def permutations(nums):
out, path, used = [], [], [False] * len(nums)
def backtrack():
if len(path) == len(nums):
out.append(path[:])
return
for i, n in enumerate(nums):
if used[i]: continue
used[i] = True
path.append(n)
backtrack()
path.pop()
used[i] = False
backtrack()
return outPattern 3: Combinations
Choose k items from n. Pick an element, recurse starting from the next index, unpick.
def combine(n, k):
out, path = [], []
def backtrack(start):
if len(path) == k:
out.append(path[:])
return
for i in range(start, n + 1):
path.append(i)
backtrack(i + 1)
path.pop()
backtrack(1)
return outPattern 4: Combination Sum
Find all combinations that sum to a target. Elements can be reused; recurse from i, not i+1.
def combination_sum(candidates, target):
out, path = [], []
def backtrack(start, remaining):
if remaining == 0:
out.append(path[:])
return
for i in range(start, len(candidates)):
if candidates[i] > remaining: continue
path.append(candidates[i])
backtrack(i, remaining - candidates[i])
path.pop()
backtrack(0, target)
return outPattern 5: Palindrome Partitioning
Split a string into substrings where each piece is a palindrome. Backtrack on cut positions.
def partition(s):
out, path = [], []
def is_pal(a, b):
while a < b:
if s[a] != s[b]: return False
a, b = a + 1, b - 1
return True
def backtrack(start):
if start == len(s):
out.append(path[:])
return
for end in range(start, len(s)):
if is_pal(start, end):
path.append(s[start:end + 1])
backtrack(end + 1)
path.pop()
backtrack(0)
return outPattern 6: Word Search on Grid
Does a word exist in a 2D grid of letters? DFS from every starting cell, mark visited, unmark on return.
def exist(board, word):
rows, cols = len(board), len(board[0])
def dfs(r, c, i):
if i == len(word): return True
if r < 0 or r >= rows or c < 0 or c >= cols: return False
if board[r][c] != word[i]: return False
tmp, board[r][c] = board[r][c], '#'
found = any(dfs(r + dr, c + dc, i + 1)
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)))
board[r][c] = tmp
return found
return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))Pattern 7: N-Queens
Place N queens on an NxN board so no two attack. Try each column in each row; use sets to track attacked columns, diagonals, and anti-diagonals.
def solve_n_queens(n):
out, cols, diag, anti = [], set(), set(), set()
board = [['.'] * n for _ in range(n)]
def backtrack(r):
if r == n:
out.append([''.join(row) for row in board])
return
for c in range(n):
if c in cols or (r - c) in diag or (r + c) in anti: continue
cols.add(c); diag.add(r - c); anti.add(r + c)
board[r][c] = 'Q'
backtrack(r + 1)
cols.remove(c); diag.remove(r - c); anti.remove(r + c)
board[r][c] = '.'
backtrack(0)
return outPattern 8: Sudoku Solver
Find an empty cell, try each digit 1 to 9, check row, column, and 3x3 box, recurse on next empty cell. Return True when no empties remain.
Pattern 9: Phone Letter Combinations
Given "23", return all letter combinations from a phone keypad. For each digit, recurse with every letter it maps to appended to the path.
def letter_combinations(digits):
if not digits: return []
mapping = {'2':'abc','3':'def','4':'ghi','5':'jkl',
'6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
out, path = [], []
def backtrack(i):
if i == len(digits):
out.append(''.join(path))
return
for ch in mapping[digits[i]]:
path.append(ch)
backtrack(i + 1)
path.pop()
backtrack(0)
return outPattern 10: Restore IP Addresses
Given "25525511135", return all valid IPv4 addresses. Backtrack on cut positions, limit each segment to 3 characters, validate each piece (0 to 255, no leading zeros except single zero).
Common pitfalls to avoid
- Appending the shared path directly to the result list. Always copy with path[:] or list(path); otherwise all your results point to the same list object.
- Forgetting the undo step. Every mutation to state before a recursive call needs a matching undo after.
- Choosing the wrong starting index for recursion. Combinations recurse with start = i + 1 (no reuse); combination sum recurses with start = i (reuse allowed). Mixing them produces duplicates or missing solutions.
- Not pruning early. Checking a constraint before recursing often saves exponential work; checking after wastes the whole branch.
- Deep copying when a swap-based approach would work. Permutations can swap in place and undo the swap, avoiding list copies entirely.
Practice sequence that works
Do subsets, permutations, and combinations first until each one takes five minutes. Then combination sum, phone letters, and palindrome partitioning. N-Queens and Sudoku last; they combine the templates with constraint tracking. Three weeks of 30 minutes a day covers all ten with confidence.
Frequently asked questions
What is the difference between backtracking and brute force?
Brute force tries every combination. Backtracking prunes the search tree by abandoning branches that cannot lead to a valid answer. Combination Sum is backtracking because we skip candidates larger than the remaining target. The savings compound exponentially on hard inputs.
Why pass path[:] instead of path?
path is a shared list across recursive calls. When you append the current path to the result, you want a snapshot of the current state. path[:] copies the list. Without the copy, the result ends up filled with references to the same list, which changes as recursion continues.
What is the time complexity of backtracking?
Depends on the problem but typically exponential. Subsets is O(2^n * n), permutations is O(n! * n), N-Queens is roughly O(n!) with pruning. The work at each leaf is the dominant factor; the recursion depth is bounded by the problem size.
How do I handle duplicates in input?
Sort the input first. In the loop, skip an element if it equals the previous one and the previous one was not just chosen. This keeps you from generating the same path through two different orderings.
When should I iterate instead of recurse?
For subsets specifically, iterating from the empty set and doubling on each new element is cleaner. For permutations, Python's itertools.permutations is already optimized. Interview judges usually want to see the recursive template because it generalizes to problems without built-in helpers.
Can I memoize a backtracking function?
Sometimes. Backtracking that produces a count or boolean can be turned into dynamic programming if subproblems repeat. Backtracking that produces all solutions cannot be memoized because each path is unique. Use memoization when the output is a single number, not a collection.
Interview day strategy
On any new backtracking problem, start by naming the template out loud: "This is subsets with constraint X" or "This is combination sum with modification Y." If you cannot name it in 60 seconds, the problem likely needs a different technique. Clarify input constraints before coding: can elements repeat, are there duplicates, is the output order sensitive. Write the recursive signature first, then the base case, then the recursive step. The undo step comes last and is easy to forget under pressure.