10 — Backtracking

Neetcode Week 8b. Backtracking is recursion that undoes its own changes. It's the standard technique for "find all configurations satisfying X" problems.

What backtracking is
The universal template
Subsets — the foundational pattern
Permutations
Combinations & Combination Sum
Word Search (grid backtracking)
N-Queens
Palindrome Partitioning
Pruning — the way to make it fast
Iterative variants and bitmask tricks
Pitfalls
Practice list

1. What backtracking is

Backtracking explores all possibilities by:

Choosing an option for the next decision.
Recursing with that choice committed.
Undoing the choice (so you can try another).

It's a depth-first search through the decision tree of partial solutions, pruning branches as soon as they can't lead to a valid answer.

Subsets of [1, 2]:

                      []                         ← root: empty subset
                     /  \
              ┌─────┘    └─────┐
              │                │
       choose 1                skip 1
              │                │
            [1]                []
            / \                / \
     choose 2  skip 2  choose 2  skip 2
         │      │        │       │
       [1,2]   [1]      [2]      []     ← leaves: complete decisions

All leaves = all subsets: [1,2], [1], [2], [].

The "undo" is what lets us reuse the same data structure across the entire DFS. Without it, we'd allocate fresh state at every branch — wasteful.

2. The universal template

def backtrack(state, choices):
    if is_solution(state):
        record(state)
        return
    
    for choice in choices(state):
        if not is_valid(choice, state):
            continue                         # pruning
        apply(choice, state)
        backtrack(state, choices)
        undo(choice, state)                  # backtrack!

The four moving parts:

State — current partial solution (a list of chosen items, a path on a grid, etc.)
Choices — what to try next, given current state.
Validity — quickly reject bad branches (the pruning).
Solution — when we've made a complete decision (record and return).

You apply this skeleton to every backtracking problem. The variations are all in what state means.

3. Subsets — the foundational pattern

Generate all 2ⁿ subsets of [1, 2, 3].

Two equivalent formulations:

Formulation A: include/exclude each element

At each step, decide whether to include nums[i].

def subsets(nums):
    res = []
    cur = []
    
    def backtrack(i):
        if i == len(nums):
            res.append(cur[:])               # snapshot
            return
        # exclude
        backtrack(i + 1)
        # include
        cur.append(nums[i])
        backtrack(i + 1)
        cur.pop()                            # undo
    
    backtrack(0)
    return res

Formulation B: at each step, pick any later element

Slightly different shape but yields the same set. Useful for combinations.

def subsets(nums):
    res = []
    cur = []
    
    def backtrack(start):
        res.append(cur[:])                   # every prefix is a valid subset
        for i in range(start, len(nums)):
            cur.append(nums[i])
            backtrack(i + 1)
            cur.pop()
    
    backtrack(0)
    return res

Both are O(n · 2ⁿ): 2ⁿ subsets, each takes O(n) to copy.

Subsets II — duplicates allowed

nums = [1, 2, 2]. Don't return [1, 2] twice.

Sort first. Skip duplicates at the same recursion depth.

def subsets_with_dup(nums):
    nums.sort()
    res = []
    cur = []
    
    def backtrack(start):
        res.append(cur[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i-1]:   # skip dup at same level
                continue
            cur.append(nums[i])
            backtrack(i + 1)
            cur.pop()
    
    backtrack(0)
    return res

The condition i > start is critical: it lets us use a duplicate once at each level, but prevents re-using it as a "new" choice at the same level.

4. Permutations

[1, 2, 3] → 6 permutations.

def permute(nums):
    res = []
    cur = []
    used = [False] * len(nums)
    
    def backtrack():
        if len(cur) == len(nums):
            res.append(cur[:])
            return
        for i in range(len(nums)):
            if used[i]: continue
            used[i] = True
            cur.append(nums[i])
            backtrack()
            cur.pop()
            used[i] = False
    
    backtrack()
    return res

Complexity: O(n · n!). There are n! permutations and copying each takes O(n).

Permutations II — duplicates

def permute_unique(nums):
    nums.sort()
    res = []
    cur = []
    used = [False] * len(nums)
    
    def backtrack():
        if len(cur) == len(nums):
            res.append(cur[:])
            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                              # use earlier duplicate first
            used[i] = True
            cur.append(nums[i])
            backtrack()
            cur.pop()
            used[i] = False
    
    backtrack()
    return res

Subtle: the condition not used[i-1] ensures we always pick the leftmost duplicate first, which prevents producing the same permutation multiple times.

5. Combinations & Combination Sum

Combinations C(n, k)

All k-element subsets.

def combine(n, k):
    res = []
    cur = []
    
    def backtrack(start):
        if len(cur) == k:
            res.append(cur[:])
            return
        for i in range(start, n + 1):
            cur.append(i)
            backtrack(i + 1)
            cur.pop()
    
    backtrack(1)
    return res

Combination Sum (Medium)

Given candidates, find all combinations that sum to target. Each candidate can be used unlimited times.

def combination_sum(candidates, target):
    res = []
    cur = []
    
    def backtrack(start, remaining):
        if remaining == 0:
            res.append(cur[:])
            return
        if remaining < 0: return              # pruning
        for i in range(start, len(candidates)):
            cur.append(candidates[i])
            backtrack(i, remaining - candidates[i])   # i (not i+1) — reuse allowed
            cur.pop()
    
    backtrack(0, target)
    return res

The i, not i+1 recursion call is what allows reuse of the same element. To disallow reuse, pass i+1.

Combination Sum II — no reuse, duplicates in candidates

def combination_sum2(candidates, target):
    candidates.sort()
    res = []
    cur = []
    
    def backtrack(start, remaining):
        if remaining == 0:
            res.append(cur[:])
            return
        for i in range(start, len(candidates)):
            if i > start and candidates[i] == candidates[i-1]:
                continue
            if candidates[i] > remaining:
                break                                  # sorted; no need to try larger
            cur.append(candidates[i])
            backtrack(i + 1, remaining - candidates[i])   # i+1: no reuse
            cur.pop()
    
    backtrack(0, target)
    return res

6. Word Search (grid backtracking)

Given grid of letters, find if word exists by adjacent letters.

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
                or board[r][c] != word[i]):
            return False
        
        board[r][c] = '#'                     # mark visited
        found = (dfs(r+1, c, i+1) or dfs(r-1, c, i+1) or
                 dfs(r, c+1, i+1) or dfs(r, c-1, i+1))
        board[r][c] = word[i]                 # restore
        return found
    
    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

Mutating the board to '#' is a common trick to mark visited cells without an external set. The undo restores the cell.

7. N-Queens

Place n queens on n×n board such that no two attack each other.

def solve_n_queens(n):
    res = []
    cols = set()
    pos_diag = set()                          # r + c
    neg_diag = set()                          # r - c
    board = [['.'] * n for _ in range(n)]
    
    def backtrack(r):
        if r == n:
            res.append([''.join(row) for row in board])
            return
        for c in range(n):
            if c in cols or (r+c) in pos_diag or (r-c) in neg_diag:
                continue
            board[r][c] = 'Q'
            cols.add(c); pos_diag.add(r+c); neg_diag.add(r-c)
            backtrack(r + 1)
            board[r][c] = '.'
            cols.discard(c); pos_diag.discard(r+c); neg_diag.discard(r-c)
    
    backtrack(0)
    return res

Key insight: queens on the same row are placed one at a time (so we move row by row). For each row, we try every column, checking for column / diagonal conflicts in O(1) using the three sets.

A diagonal where r + c is constant is one of the negative-slope diagonals. Where r - c is constant is one of the positive-slope diagonals.

8. Palindrome Partitioning

Partition s into substrings, each a palindrome. Return all such partitions.

def partition(s):
    res = []
    cur = []
    
    def is_pal(l, r):
        while l < r:
            if s[l] != s[r]: return False
            l += 1; r -= 1
        return True
    
    def backtrack(i):
        if i == len(s):
            res.append(cur[:])
            return
        for j in range(i, len(s)):
            if is_pal(i, j):
                cur.append(s[i:j+1])
                backtrack(j + 1)
                cur.pop()
    
    backtrack(0)
    return res

For each starting index, try every ending; if the substring is a palindrome, recurse on the rest.

9. Pruning

A backtracking solution without pruning is just brute-force enumeration. Pruning is what makes it fast.

Three classic prunes

Domain prune — eliminate values that can't lead to a solution.

if remaining < 0: return                  # can't undo a too-large pick

Symmetry prune — skip equivalent branches.

if i > start and nums[i] == nums[i-1]: continue

Bound prune — propagate constraints (sudoku, n-queens).
```
if c in cols_used: continue
```

Sort first

Sorting candidates often enables an early break:

for i in range(start, len(candidates)):
    if candidates[i] > remaining: break       # sorted; rest are too big

Memoization → DP

If you find that "subproblems repeat," backtracking with memoization morphs into Dynamic Programming. Word Break, Decode Ways, etc. all fit this pattern.

10. Iterative variants

Generate all subsets iteratively

def subsets(nums):
    res = [[]]
    for x in nums:
        res += [s + [x] for s in res]
    return res

For each new element, double the result by adding new sets that include it.

Bitmask subsets (n ≤ 30)

def subsets(nums):
    res = []
    n = len(nums)
    for mask in range(1 << n):                # 2^n masks
        subset = [nums[i] for i in range(n) if mask & (1 << i)]
        res.append(subset)
    return res

Each bit position represents inclusion of one element. See 16-bit-manipulation.md for more.

11. Pitfalls

Forgetting to undo

cur.append(x)
backtrack(i + 1)
# cur.pop()    ← MISSING

Each branch will pollute the next.

Snapshot vs reference

res.append(cur)        # ❌ stores a reference; mutations leak
res.append(cur[:])     # ✅ snapshot of current state
res.append(list(cur))  # ✅ same idea

Modifying input

If the problem says "don't modify input," you can't use the board[r][c] = '#' trick. Use an external visited set.

Time blow-up

Backtracking has exponential time in the worst case. For n > 20 and no pruning, you're typically wrong — pivot to DP or a polynomial algorithm.

Stack overflow

Deep recursion (n > 10⁴) can crash Python. sys.setrecursionlimit(10**6) or refactor to iterative.

Skipping duplicates incorrectly

The if i > start and nums[i] == nums[i-1] only works after sorting. Without sort, duplicates aren't adjacent and you can't dedupe this way.

Choosing the wrong recursion structure

Subsets vs permutations differ in whether order matters. Combinations are subsets of fixed size. Read carefully — bug magnet.

12. Practice list

#	Problem	Pattern	Difficulty
78	Subsets	Power set	Medium
90	Subsets II	Power set with dups	Medium
39	Combination Sum	Reuse	Medium
40	Combination Sum II	No-reuse + dedup	Medium
46	Permutations	All orderings	Medium
47	Permutations II	With dups	Medium
79	Word Search	Grid DFS	Medium
131	Palindrome Partitioning	String partitioning	Medium
17	Letter Combinations of Phone Number	Cartesian product	Medium
51	N-Queens	Constraint sets	Hard
22	Generate Parentheses	Constrained build	Medium
37	Sudoku Solver	Big constraint set	Hard

TL;DR ✅

Backtracking = DFS with undo. State is a list (or grid mark) you mutate and restore.
Universal template: if base_case: record; for choice: apply, recurse, undo.
Subsets = include/exclude per element. Permutations = use boolean used[]. Combinations = use start index.
Dedup duplicates by sorting first, then skipping nums[i] == nums[i-1] at same level.
Pruning is what turns brute force into a workable algorithm — sort + early break + symmetry skip.
Snapshot results (cur[:]), don't store mutable references.
For grid backtracking, mutate-then-restore the cell for an O(1) visited-set.

Next: 11-graphs.md.

External resources

NeetCode Backtracking playlist: https://www.youtube.com/playlist?list=PLot-Xpze53lf5C3HSjCnyFghlW0G1HHXo
"Backtracking template" article: https://leetcode.com/problems/permutations/discuss/18239/A-general-approach-to-backtracking-questions-in-Java
N-Queens visualization: https://www.cs.usfca.edu/~galles/visualization/RecQueens.html