Recursion and Backtracking

Backtracking is organised trial and error. You build a solution one choice at a time, and as soon as a partial solution cannot lead to a valid answer, you undo the last choice and try the next one. It is the standard tool for generating all subsets, permutations and combinations, solving puzzles such as N-Queens and Sudoku, and searching a grid for a word. The code is a short template. The skill is deciding what a "choice" is, what makes a partial solution invalid, and how to avoid generating duplicates.

1. When this pattern applies

• The problem asks for all solutions: all subsets, all permutations, all valid parenthesisations.
• You must find any solution to a constraint puzzle, where a systematic search with pruning is the only known way.
• The input size is small (often $n\le 20$), a strong hint that an exponential search is intended.
• The solution is built step by step, and each step has a small number of options.

2. The template

Think of the search as a tree of decisions. Each node is a partial solution, each edge is a choice, each leaf is a complete solution (or a dead end). Backtracking is a depth-first walk of that tree.

def backtrack(state):
    if is_complete(state):
        record(state)
        return
    for choice in choices(state):
        if is_valid(state, choice):      # prune: skip invalid branches early
            apply(state, choice)         # choose
            backtrack(state)             # explore
            undo(state, choice)          # un-choose (backtrack)

The three phases, choose, explore, un-choose, are the pattern. The undo step restores shared state so the next choice starts clean. Forgetting it is the most common bug.

3. Subsets

For each element, either include it or not, giving $2^n$ subsets. The decision tree has depth $n$.

def subsets(nums):
    result, current = [], []
    def backtrack(i):
        if i == len(nums):
            result.append(current[:])          # copy: current keeps changing
            return
        current.append(nums[i])                # choice 1: include nums[i]
        backtrack(i + 1)
        current.pop()                          # undo
        backtrack(i + 1)                       # choice 2: exclude nums[i]
    backtrack(0)
    return result

assert sorted(subsets([1, 2, 3])) == sorted([[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]])
assert subsets([]) == [[]]

Always copy the current state when recording it (current[:]), because the same list is mutated as the search continues. Appending current itself stores a reference that will be emptied.

Time $O(n\cdot 2^n)$: $2^n$ subsets, each up to $n$ long to copy. You cannot do better because the output has that size. Space $O(n)$ for the recursion, besides the output.

An iterative alternative builds subsets by doubling: for each element, add it to every existing subset.

def subsets_iterative(nums):
    result = [[]]
    for x in nums:
        result += [s + [x] for s in result]
    return result

assert sorted(subsets_iterative([1, 2, 3])) == sorted(subsets([1, 2, 3]))

Subsets with duplicates. To avoid duplicate subsets, sort the input and skip an element that equals the previous one at the same decision level.

def subsets_with_dup(nums):
    nums.sort()
    result, current = [], []
    def backtrack(start):
        result.append(current[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:      # same value already tried at this level
                continue
            current.append(nums[i])
            backtrack(i + 1)
            current.pop()
    backtrack(0)
    return result

assert sorted(subsets_with_dup([1, 2, 2])) == sorted([[], [1], [1, 2], [1, 2, 2], [2], [2, 2]])

This formulation, a loop over candidates starting from start, is the standard way to build combinations, and it records a result at every node.

4. Combinations and combination sum

Combinations of $k$ numbers from $\mathrm{1..}n$: choose in increasing order, so each combination is generated once.

def combine(n, k):
    result, current = [], []
    def backtrack(start):
        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

assert combine(4, 2) == [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
assert combine(1, 1) == [[1]]

Prune when the remaining numbers cannot fill the combination: only loop while n - i + 1 >= k - len(current). It makes the search faster without changing the output.

Combination sum. Find combinations of distinct numbers that sum to a target, where a number may be reused. Passing i (not i + 1) allows reuse. Pruning stops when the remaining target goes negative, and sorting the candidates allows stopping the loop early.

def combination_sum(candidates, target):
    candidates.sort()
    result, current = [], []
    def backtrack(start, remaining):
        if remaining == 0:
            result.append(current[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break                                   # sorted: nothing later fits either
            current.append(candidates[i])
            backtrack(i, remaining - candidates[i])     # i, not i+1: reuse is allowed
            current.pop()
    backtrack(0, target)
    return result

assert sorted(combination_sum([2, 3, 6, 7], 7)) == [[2, 2, 3], [7]]
assert sorted(combination_sum([2, 3, 5], 8)) == [[2, 2, 2, 2], [2, 3, 3], [3, 5]]
assert combination_sum([2], 1) == []

Combination sum II (each number used once, with duplicates in the input) combines both ideas: sort, advance with i + 1, and skip equal values at the same level.

def combination_sum2(candidates, target):
    candidates.sort()
    result, current = [], []
    def backtrack(start, remaining):
        if remaining == 0:
            result.append(current[:])
            return
        for i in range(start, len(candidates)):
            if i > start and candidates[i] == candidates[i - 1]:
                continue
            if candidates[i] > remaining:
                break
            current.append(candidates[i])
            backtrack(i + 1, remaining - candidates[i])
            current.pop()
    backtrack(0, target)
    return result

assert sorted(combination_sum2([10, 1, 2, 7, 6, 1, 5], 8)) == [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]

5. Permutations

All orderings of $n$ items: $n!$ results. At each position, choose any item not yet used. Track a used array.

def permutations(nums):
    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
            current.append(nums[i])
            backtrack()
            current.pop()
            used[i] = False
    backtrack()
    return result

assert sorted(permutations([1, 2, 3])) == [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
assert permutations([1]) == [[1]]

Permutations with duplicates: sort, and skip a value that equals the previous one if the previous one is unused (it means we are about to repeat a choice at the same level).

def permutations_unique(nums):
    nums.sort()
    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
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue                               # avoid a duplicate branch
            used[i] = True
            current.append(nums[i])
            backtrack()
            current.pop()
            used[i] = False
    backtrack()
    return result

assert sorted(permutations_unique([1, 1, 2])) == [[1, 1, 2], [1, 2, 1], [2, 1, 1]]

6. Constraint puzzles: N-Queens

Place $n$ queens on an $n\times n$ board so none attack each other. Place one queen per row. A column or diagonal is under attack if a queen already occupies it. Track occupied columns and the two diagonal directions in sets: the row minus column is constant along one diagonal, and the row plus column along the other.

def solve_n_queens(n):
    result = []
    cols, diag1, diag2 = set(), set(), set()
    placement = []                                     # placement[r] = column of the queen in row r
    def backtrack(r):
        if r == n:
            result.append(["." * c + "Q" + "." * (n - c - 1) for c in placement])
            return
        for c in range(n):
            if c in cols or (r - c) in diag1 or (r + c) in diag2:
                continue                               # prune: this square is attacked
            cols.add(c); diag1.add(r - c); diag2.add(r + c)
            placement.append(c)
            backtrack(r + 1)
            placement.pop()
            cols.remove(c); diag1.remove(r - c); diag2.remove(r + c)
    backtrack(0)
    return result

assert len(solve_n_queens(4)) == 2
assert len(solve_n_queens(6)) == 4
assert len(solve_n_queens(8)) == 92
assert solve_n_queens(1) == [["Q"]]

The sets make each safety check $O(1)$. Without pruning, the search would try $n^n$ placements, and with it far fewer.

Sudoku uses the same shape: pick an empty cell, try digits 1 to 9 that do not violate row, column or box constraints, recurse, undo on failure. The speed-up is to choose the cell with the fewest remaining options first.

7. Searching a grid: word search

Does a word exist in a grid by moving to adjacent cells, using each cell at most once per word? DFS from every cell that matches the first letter. Mark the cell as used while exploring, and restore it afterwards.

def exist(board, word):
    rows, cols = len(board), len(board[0])
    def dfs(r, c, i):
        if i == len(word):
            return True
        if not (0 <= r < rows and 0 <= c < cols) or board[r][c] != word[i]:
            return False
        saved, board[r][c] = 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] = saved                            # un-choose
        return found
    return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))

b = [list("ABCE"), list("SFCS"), list("ADEE")]
assert exist(b, "ABCCED") is True
assert exist(b, "SEE") is True
assert exist(b, "ABCB") is False

Time $O(R\cdot C\cdot 3^L)$ for a word of length $L$: from each start, up to 3 directions after the first step. A trie speeds up searching for many words at once (see the tries chapter).

8. Generating structured strings

Generate parentheses. Produce all well-formed strings with $n$ pairs. Track how many opens and closes remain: you may add ( if opens remain, and ) only if more ( than ) have been placed. The invariants prune invalid strings so only valid ones are generated, which is the Catalan number of them.

def generate_parentheses(n):
    result = []
    def backtrack(current, opened, closed):
        if len(current) == 2 * n:
            result.append(current)
            return
        if opened < n:
            backtrack(current + "(", opened + 1, closed)
        if closed < opened:
            backtrack(current + ")", opened, closed + 1)
    backtrack("", 0, 0)
    return result

assert sorted(generate_parentheses(3)) == sorted(["((()))", "(()())", "(())()", "()(())", "()()()"])
assert generate_parentheses(1) == ["()"]

Strings are immutable in Python, so passing current + "(" creates a new string, and no explicit undo is needed. That is a valid style: immutable state needs no undo.

Letter combinations of a phone number. For each digit, choose one of its letters.

def letter_combinations(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(i, current):
        if i == len(digits):
            result.append(current)
            return
        for ch in phone[digits[i]]:
            backtrack(i + 1, current + ch)
    backtrack(0, "")
    return result

assert sorted(letter_combinations("23")) == ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
assert letter_combinations("") == []

Palindrome partitioning. Split a string into pieces that are all palindromes. At each position, try each prefix that is a palindrome and recurse on the rest.

def partition_palindromes(s):
    result, current = [], []
    def backtrack(start):
        if start == len(s):
            result.append(current[:])
            return
        for end in range(start + 1, len(s) + 1):
            piece = s[start:end]
            if piece == piece[::-1]:                  # prune: only palindromic prefixes
                current.append(piece)
                backtrack(end)
                current.pop()
    backtrack(0)
    return result

assert sorted(partition_palindromes("aab")) == [["a", "a", "b"], ["aa", "b"]]
assert partition_palindromes("a") == [["a"]]

9. Analysing and speeding up backtracking

Complexity is the number of nodes in the decision tree times the work per node. Subsets: $2^n$ leaves. Permutations: $n!$. Combinations of $k$ from $n$: $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$. State these, and mention that the output size is itself a lower bound.

Ways to make it faster:

1. Prune early. Check constraints before recursing, not at the leaf.
2. Order choices well. Sorted candidates let you break instead of continue. For puzzles, try the most constrained choice first.
3. Avoid duplicates by construction with sorting and skipping, instead of generating duplicates and deduplicating with a set.
4. Use sets or arrays for $O(1)$ validity checks rather than rescanning the state.
5. Memoise when subproblems repeat. If many different paths reach the same state, you are really facing dynamic programming (next chapters), for example word break, and not a pure enumeration.

Backtracking versus dynamic programming. If you must list all solutions, backtracking is required. If you need only a count or the best value, and states repeat, dynamic programming is far faster. Recognising which you need is a key interview judgement.

10. Common mistakes

• Forgetting to undo a choice, so state leaks into the next branch.
• Appending the mutable state itself to the results, instead of a copy.
• Duplicates in the output because the input has repeated values and you did not sort and skip.
• Skipping with the wrong condition, such as i > 0 instead of i > start, which wrongly removes valid branches.
• No pruning, making a feasible problem time out.
• Reusing versus not reusing elements: backtrack(i) versus backtrack(i + 1).
• Recursion depth problems on deep searches in Python. Backtracking depth is usually small, but check.
• Using backtracking for counting or optimisation where dynamic programming is polynomial.

11. Practice set

1. Subsets, subsets II, combinations, combination sum I, II and III.
2. Permutations, permutations II, next permutation (an algorithm, not backtracking).
3. Generate parentheses, letter combinations of a phone number.
4. Palindrome partitioning, restore IP addresses.
5. N-Queens, N-Queens II (count only).
6. Word search, word search II (with a trie).
7. Sudoku solver, valid sudoku (not backtracking).
8. Partition to $k$ equal sum subsets, matchsticks to square.
9. Expression add operators, additive number.
10. Gray code and the Tower of Hanoi (recursion without choices).