13. Backtracking

Backtracking is recursion with choices. At each step, you make a choice, explore what happens, then undo the choice and try the next option. It's how you systematically explore all possibilities without missing any — and prune branches that can't lead to valid solutions.

The Template

Every backtracking problem follows this structure:

def backtrack(state, choices):
    if is_complete(state):
        results.append(state[:])  # copy the current state
        return
    for choice in choices:
        if is_valid(choice):
            state.append(choice)      # choose
            backtrack(state, choices)  # explore
            state.pop()               # unchoose (backtrack)

Choose → Explore → Unchoose. The "unchoose" step is what makes it backtracking — you restore state so the next iteration starts fresh.

Subsets (All Combinations)

Generate all subsets of a set. At each element, choose to include it or not.

LeetCode 78 - Subsets

def subsets(nums: list[int]) -> list[list[int]]:
    result = []
    current = []

    def backtrack(start: int):
        result.append(current[:])  # every state is a valid subset
        for i in range(start, len(nums)):
            current.append(nums[i])   # choose
            backtrack(i + 1)          # explore
            current.pop()             # unchoose

    backtrack(0)
    return result

# Input: [1,2,3]
# Output: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

The output follows a DFS preorder traversal of the decision tree — process the node (append to results), then explore children (loop), then return (pop):

            []
         /  |  \
       [1] [2] [3]
       / \    \
   [1,2] [1,3] [2,3]
     |
  [1,2,3]

Each node is one backtrack() call = one append to results. Going back up = pop().

Permutations (All Orderings)

Generate all orderings of a set. At each position, try every unused element.

Key difference from subsets: In subsets, start prevents going backward — you only pick elements after the current index. In permutations, any element can go in any position, so you loop from 0 every time. The used array prevents picking the same element twice in one permutation.

Decision tree for [1, 2, 3]:

                        []
                /       |       \
             [1]       [2]       [3]
            /   \     /   \     /   \
         [1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
           |     |     |     |     |     |
       [1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]  ← only leaves are results

LeetCode 46 - Permutations

def permutations(nums: list[int]) -> list[list[int]]:
    result = []
    current = []
    used = [False] * len(nums)

    def backtrack():
        if len(current) == len(nums):
            result.append(current[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True              # choose
            current.append(nums[i])
            backtrack()                  # explore
            current.pop()               # unchoose
            used[i] = False

    backtrack()
    return result

# Input: [1,2,3]
# Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Combinations (Choose K from N)

Pick K elements from N without regard to order. Like subsets, but stop when you've picked exactly K.

Uses start (like subsets) to avoid duplicates — [1,2] and [2,1] are the same combination, so only pick forward.

LeetCode 77 - Combinations

def combine(n: int, k: int) -> list[list[int]]:
    result = []
    current = []

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

    backtrack(1)
    return result

Decision tree for n=4, k=2:

          []
      / / | \
    [1] [2] [3] [4]
    /|\   |\    \
 [1,2][1,3][1,4] [2,3][2,4] [3,4]  ← only collect when len==k

Pruning

Pruning means skipping branches that can't lead to valid solutions. It's what makes backtracking practical — without pruning, you'd explore every possible path (exponential).

The idea: Before exploring a choice, check if it's even possible to reach a valid solution from here. If not, break or continue — don't recurse.

LeetCode 39 - Combination Sum

Find all combinations of candidates that sum to target. Elements may be reused.

def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    result = []
    current = []
    candidates.sort()  # sort to enable pruning

    def backtrack(start: int, remaining: int):
        if remaining == 0:
            result.append(current[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break  # PRUNE: sorted, so all remaining candidates are also too large
            current.append(candidates[i])
            backtrack(i, remaining - candidates[i])  # i (not i+1) — can reuse same element
            current.pop()

    backtrack(0, target)
    return result

Why sort? So the break works. If sorted, candidates[i] > remaining guarantees everything after is also too large — skip them all. Without sorting, you'd need continue (skip just this one) and check every element — slower but same result.

Why backtrack(i, ...) instead of backtrack(i+1, ...)? Because elements can be reused. backtrack(i) means "try this element again." For problems where each element can only be used once, use backtrack(i+1).

Backtracking vs DP

Both explore choices. The difference:

If the problem says "generate all..." or "find all valid..." → backtracking. If the problem says "find the minimum/maximum" with overlapping subproblems → DP.

N-Queens (Classic Backtracking)

Place N queens on an N×N board so no two attack each other (no shared row, column, or diagonal).

Approach: Place one queen per row. For each row, try each column. Prune immediately if the column or either diagonal is already occupied.

Why row - col and row + col? All cells on the same diagonal share the same row - col value (↘ direction) or row + col value (↙ direction). Storing these in sets gives O(1) conflict checking.

4×4 board, row-col values:     row+col values:
  0  -1  -2  -3                 0  1  2  3
  1   0  -1  -2                 1  2  3  4
  2   1   0  -1                 2  3  4  5
  3   2   1   0                 3  4  5  6

LeetCode 51 - N-Queens

def solve_n_queens(n: int) -> int:
    count = 0
    cols = set()
    diag1 = set()  # row - col
    diag2 = set()  # row + col

    def backtrack(row: int):
        nonlocal count
        if row == n:
            count += 1
            return
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue  # prune: position attacked
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            backtrack(row + 1)
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)

    backtrack(0)
    return count

Python's sets give O(1) lookup for constraint checking — cleaner than boolean arrays.

Time Complexity

Backtracking is exponential — you're exploring a decision tree. The size depends on the branching factor:

Pruning doesn't change the complexity class — it reduces the constant. A well-pruned O(n!) is still O(n!), just with a smaller multiplier. But in practice, pruning can cut 90%+ of branches.

Space: O(n) for the recursion stack depth (height of the decision tree) + O(results) for storing solutions.

Practice Problems

Key Takeaways

• Backtracking = recursion with choose → explore → unchoose
• Three core problems: subsets (include/exclude), permutations (all orderings), combinations (choose K)
• Pruning makes backtracking practical — skip branches that can't lead to valid solutions
• Sorting enables pruning by allowing early termination
• Python sets provide clean O(1) constraint checking (N-Queens, Sudoku)
• Backtracking generates ALL solutions; DP finds ONE optimal solution
• Time complexity is exponential (O(2ⁿ) for subsets, O(n!) for permutations) — pruning reduces the constant but not the class