Pattern 11 · Recursion
Backtracking
Try something. If it doesn't work, undo it and try something else. Backtracking explores every possible solution by making a choice, recursing deeper, then reversing the choice — abandoning a path the moment it can't lead to a valid answer.
time O(2ⁿ) – O(n!)space O(n)variants subsets · perms · boardspractice 13 problems
01 core concept
Choose, explore, unchoose
Every backtracking algorithm walks a decision tree. At each node you choose an option, explore (recurse) with that choice in place, then unchoose — restore the state exactly as it was — before trying the next option.
[]
/ | \
[1] [2] [3] ← CHOOSE
/ \ |
[1,2] [1,3] [2,3] ← EXPLORE
|
[1,2,3] ← BASE CASE (solution found)
|
backtrack → remove 3 → [1,2] ← UNCHOOSE
The key insight
Solutions are built incrementally, and a path is abandoned as soon as
it cannot lead to a valid solution. That early abandonment is called pruning —
it's what separates backtracking from blind brute force.
step 1 / 12walkthrough — all subsets of [1, 2, 3]
path []
found 1
backtrack(0, []) begins. In the subsets tree every node is a valid answer, so we record [] immediately, then loop i = 0..2.
02 recognition
When to reach for it
| Signal in problem | Example problem |
|---|---|
| "Generate ALL permutations / combinations" | Permutations, Subsets |
| "Find ALL valid configurations" | N-Queens, Sudoku |
| "All possible paths / ways" | Word Search, Palindrome Partitioning |
| "Constraint satisfaction" | Sudoku, Crossword |
| Input size is SMALL (n ≤ ~15–20) | Most backtracking problems |
Red flag
If n is large (> 25), backtracking alone is almost certainly TLE. Exponential search only
survives on small inputs — the constraint section of the problem is telling you which pattern to use.
Backtracking vs. DFS vs. DP
| Backtracking | DFS | DP |
|---|---|---|
| Generate ALL valid solutions | Explore a structure (tree, graph) | Find OPTIMAL solution with overlapping subproblems |
| Explicit UNDO step (backtrack) | May not need undo | Stores results (memo / table) |
| Exponential time | O(V + E) typically | Polynomial (often) |
03 the template
One template, four questions
Every backtracking problem follows the Choose → Explore → Unchoose skeleton:
backtrack_template.pypython
def backtrack(candidates, path, result, start):
# BASE CASE: when is a solution complete?
if is_complete(path):
result.append(path[:]) # IMPORTANT: append a COPY
return
for i in range(start, len(candidates)):
# PRUNE: skip invalid choices early
if not is_valid(candidates[i], path):
continue
# CHOOSE
path.append(candidates[i])
# EXPLORE (recurse)
backtrack(candidates, path, result, i + 1) # i+1 or i depending on reuse
# UNCHOOSE (backtrack)
path.pop()Strategy framework — answer these before coding
- CHOICES — what options do I have at each step? (elements to include, positions to place)
- CONSTRAINTS — when should I prune? (duplicates, exceeded target, invalid state)
- GOAL — when is a solution complete? (path length = n, target reached, board full)
- UNDO — how do I reverse a choice? (
path.pop(), unmark visited, restore cell)
04 duplicates
Handling duplicate values
When the input has duplicate values and you need unique results: sort first, then skip consecutive duplicates at the same decision level.
duplicate skip idiompython
nums.sort() # MUST sort first
def backtrack(start, path):
result.append(path[:])
for i in range(start, len(nums)):
# Skip duplicate at same decision level
if i > start and nums[i] == nums[i - 1]:
continue
path.append(nums[i])
backtrack(i + 1, path)
path.pop()Which branches get pruned for [1, 2, 2]:
[]
/ | \
[1] [2] [2] ← SKIP (i>start, nums[2]==nums[1])
/ \ |
[1,2] [1,2] [2,2]
← SKIP
|
[1,2,2]
The condition i > start is the subtle part: it allows the first occurrence
of a value at each level (going deeper) but blocks the second occurrence at the same level
(a sibling branch that would rebuild identical subsets).
05 worked solutions
The canonical problems
LC 78Subsets — include/exclude
subsets.pypython
def subsets(nums):
result = []
def backtrack(start, path):
result.append(path[:]) # every path is a valid subset
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
# Result for [1,2,3]:
# [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3] — 2^3 = 8 subsetsLC 90Subsets II — with duplicates
subsets_ii.pypython
def subsetsWithDup(nums):
nums.sort()
result = []
def backtrack(start, path):
result.append(path[:])
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i - 1]:
continue # skip duplicate at same level
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return resultLC 46Permutations
permutations.pypython
def permute(nums):
result = []
def backtrack(path, remaining):
if not remaining:
result.append(path[:])
return
for i in range(len(remaining)):
path.append(remaining[i])
backtrack(path, remaining[:i] + remaining[i+1:])
path.pop()
backtrack([], nums)
return resultThe choices shrink at each level — pick one, recurse on what's left:
Remaining: {1,2,3} {1,2,3} {1,2,3}
Choose: 1 2 3
| | |
Remaining: {2,3} {1,3} {1,2}
Choose: 2 3 1 3 1 2
| | | | | |
Remaining: {3} {2} {3} {1} {2} {1}
Choose: 3 2 3 1 2 1
| | | | | |
Result: [1,2,3][1,3,2] [2,1,3][2,3,1] [3,1,2][3,2,1]
Total = 3! = 6 permutations
LC 47Permutations II — with duplicates
permutations_ii.pypython
def permuteUnique(nums):
nums.sort()
result = []
used = [False] * len(nums)
def backtrack(path):
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
# Skip duplicate: same value, previous wasn't used at this level
if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
continue
used[i] = True
path.append(nums[i])
backtrack(path)
path.pop()
used[i] = False
backtrack([])
return resultLC 39Combination Sum — reuse allowed
combination_sum.pypython
def combinationSum(candidates, target):
result = []
def backtrack(start, path, remaining):
if remaining == 0:
result.append(path[:])
return
if remaining < 0:
return # PRUNE
for i in range(start, len(candidates)):
path.append(candidates[i])
backtrack(i, path, remaining - candidates[i]) # i, NOT i+1 (reuse!)
path.pop()
backtrack(0, [], target)
return resultLC 40Combination Sum II — no reuse, skip duplicates
combination_sum_ii.pypython
def combinationSum2(candidates, target):
candidates.sort()
result = []
def backtrack(start, path, remaining):
if remaining == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
if candidates[i] > remaining:
break # PRUNE: sorted, so all future too large
if i > start and candidates[i] == candidates[i - 1]:
continue # skip duplicates
path.append(candidates[i])
backtrack(i + 1, path, remaining - candidates[i])
path.pop()
backtrack(0, [], target)
return resultLC 22Generate Parentheses — constraint counting
generate_parentheses.pypython
def generateParenthesis(n):
result = []
def backtrack(path, open_count, close_count):
if len(path) == 2 * n:
result.append("".join(path))
return
if open_count < n: # can still add '('
path.append("(")
backtrack(path, open_count + 1, close_count)
path.pop()
if close_count < open_count: # can add ')' only if open > close
path.append(")")
backtrack(path, open_count, close_count + 1)
path.pop()
backtrack([], 0, 0)
return resultThe two constraints
open_count < n → can add '('.
close_count < open_count → can add ')'.
For n = 2: after "((" only ')' is allowed; after "()"
only '(' is. The valid strings "(())" and "()()" fall out of the constraints —
no validity check needed at the end.
LC 51N-Queens — board constraint sets
n_queens.pypython
def solveNQueens(n):
result = []
cols = set() # columns with queens
diag1 = set() # row - col (anti-diagonal)
diag2 = set() # row + col (main 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 # PRUNE: conflict
# CHOOSE
board[row][col] = "Q"
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
backtrack(row + 1, board)
# UNCHOOSE
board[row][col] = "."
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
board = [["." for _ in range(n)] for _ in range(n)]
backtrack(0, board)
return resultOne solution to 4-Queens, with the constraint sets tracked per placement:
col: 0 1 2 3
+---+---+---+---+
row 0: | | Q | | | cols={1}, diag1={-1}, diag2={1}
+---+---+---+---+
row 1: | | | | Q | col=3 ok? 3 not in cols ✓
+---+---+---+---+ row-col = -2 not in diag1 ✓
row 2: | Q | | | | row+col = 4 not in diag2 ✓
+---+---+---+---+
row 3: | | | Q | |
+---+---+---+---+
Three O(1) set lookups replace scanning the whole board for conflicts — one queen per row is implicit (we recurse row by row), so only columns and the two diagonals need checking.
LC 79Word Search — grid + visited marking
word_search.pypython
def exist(board, word):
rows, cols = len(board), len(board[0])
def backtrack(r, c, idx):
if idx == len(word):
return True
if (r < 0 or r >= rows or c < 0 or c >= cols
or board[r][c] != word[idx]):
return False
# CHOOSE: mark visited
temp = board[r][c]
board[r][c] = "#"
# EXPLORE all 4 directions
found = (backtrack(r + 1, c, idx + 1) or
backtrack(r - 1, c, idx + 1) or
backtrack(r, c + 1, idx + 1) or
backtrack(r, c - 1, idx + 1))
# UNCHOOSE: restore cell
board[r][c] = temp
return found
for r in range(rows):
for c in range(cols):
if backtrack(r, c, 0):
return True
return FalseLC 17Letter Combinations of a Phone Number
letter_combinations.pypython
def letterCombinations(digits):
if not digits:
return []
phone = {
"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
"6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"
}
result = []
def backtrack(idx, path):
if idx == len(digits):
result.append("".join(path))
return
for ch in phone[digits[idx]]:
path.append(ch)
backtrack(idx + 1, path)
path.pop()
backtrack(0, [])
return result06 complexity
Complexity reference
| Problem | Time | Space | Notes |
|---|---|---|---|
| Subsets | O(n · 2ⁿ) | O(n) | 2ⁿ subsets, copy costs O(n) |
| Subsets II | O(n · 2ⁿ) | O(n) | With pruning |
| Permutations | O(n · n!) | O(n) | n! permutations |
| Permutations II | O(n · n!) | O(n) | With pruning |
| Combination Sum | O(n^(T/M)) | O(T/M) | T = target, M = min candidate |
| Generate Parentheses | O(4ⁿ / √n) | O(n) | Catalan number |
| N-Queens | O(n!) | O(n) | Constraint pruning helps |
| Word Search | O(m·n · 3ᴸ) | O(L) | L = word length, 3 directions |
| Letter Combinations | O(4ⁿ) | O(n) | n = digits length |
07 common mistakes
Where backtracking goes wrong
Mistake 1 — forgetting to copy the path
result.append(path[:]) NOT result.append(path).
path is a reference that keeps mutating as recursion continues —
without the copy you end up with a list of empty lists.
Mistake 2 — not undoing the choice
Every path.append() needs a matching path.pop().
Every visited.add() needs a matching visited.remove().
An unbalanced choose/unchoose corrupts every sibling branch that follows.
Mistake 3 — wrong start index
Subsets / Combinations: recurse with i + 1 (no reuse).
Combination Sum (reuse allowed): recurse with i (same element again).
Permutations: always start at 0, but skip used elements.
Mistake 4 — duplicate handling without sorting
The skip logic nums[i] == nums[i-1] only works when the array is
sorted first — equal values must be adjacent for the comparison to see them.
Mistake 5 — modifying the input without restoring
In Word Search, if you mark cells visited with "#", you MUST restore them on
backtrack — otherwise other starting positions see a vandalized board.
10 practice
Practice ladder
In this order — easiest first. Tick each one as you solve it, and re-solve anything that took more than 25 minutes two days later.
13 problems