8. Recursion & Backtracking

Key Insight

Backtracking = DFS on a decision tree with pruning. Every backtracking solution follows the same template: make a choice → recurse → undo the choice. The art is in writing tight pruning conditions to avoid exploring dead branches.

8.1 Backtracking Template

def backtrack(state, choices, result):
    if is_solution(state):
        result.append(state[:])   # snapshot — don't append the mutable reference
        return
    for choice in choices:
        if is_valid(state, choice):
            state.append(choice)           # make choice
            backtrack(state, choices, result)
            state.pop()                    # undo choice

---

8.2 Subsets, Permutations, Combinations

# --- All subsets (power set) ---
def subsets(nums: list[int]) -> list[list[int]]:
    res, path = [], []
    def bt(start: int):
        res.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            bt(i + 1)
            path.pop()
    bt(0)
    return res

# --- Subsets with duplicates ---
def subsets_with_dup(nums: list[int]) -> list[list[int]]:
    nums.sort()
    res, path = [], []
    def bt(start: int):
        res.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i-1]:
                continue   # skip duplicates at same depth
            path.append(nums[i])
            bt(i + 1)
            path.pop()
    bt(0)
    return res

# --- All permutations ---
def permutations(nums: list[int]) -> list[list[int]]:
    res, path = [], []
    used = [False] * len(nums)
    def bt():
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i, x in enumerate(nums):
            if used[i]:
                continue
            if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
                continue   # dedup for repeated elements
            used[i] = True
            path.append(x)
            bt()
            path.pop()
            used[i] = False
    bt()
    return res

# --- Combinations (choose k from n) ---
def combinations(n: int, k: int) -> list[list[int]]:
    res, path = [], []
    def bt(start: int):
        if len(path) == k:
            res.append(path[:])
            return
        # Pruning: not enough elements left
        for i in range(start, n - (k - len(path)) + 2):
            path.append(i)
            bt(i + 1)
            path.pop()
    bt(1)
    return res

# --- Combination sum (reuse allowed, distinct candidates) ---
def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    res, path = [], []
    candidates.sort()
    def bt(start: int, remaining: int):
        if remaining == 0:
            res.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break   # pruning: sorted, so rest are larger
            path.append(candidates[i])
            bt(i, remaining - candidates[i])   # i (not i+1) allows reuse
            path.pop()
    bt(0, target)
    return res

---

8.3 Classic Backtracking Problems

# --- N-Queens ---
def solve_n_queens(n: int) -> list[list[str]]:
    res = []
    cols = set(); pos_diag = set(); neg_diag = set()
    board = [['.']*n for _ in range(n)]

    def bt(row: int):
        if row == n:
            res.append([''.join(r) for r in board])
            return
        for col in range(n):
            if col in cols or (row+col) in pos_diag or (row-col) in neg_diag:
                continue
            cols.add(col); pos_diag.add(row+col); neg_diag.add(row-col)
            board[row][col] = 'Q'
            bt(row + 1)
            board[row][col] = '.'
            cols.remove(col); pos_diag.remove(row+col); neg_diag.remove(row-col)
    bt(0)
    return res

# --- Sudoku solver ---
def solve_sudoku(board: list[list[str]]) -> None:
    rows    = [set() for _ in range(9)]
    cols    = [set() for _ in range(9)]
    boxes   = [set() for _ in range(9)]
    empties = []
    for r in range(9):
        for c in range(9):
            if board[r][c] != '.':
                d = board[r][c]
                rows[r].add(d); cols[c].add(d); boxes[(r//3)*3+c//3].add(d)
            else:
                empties.append((r, c))

    def bt(idx: int) -> bool:
        if idx == len(empties):
            return True
        r, c = empties[idx]
        b = (r//3)*3 + c//3
        for d in '123456789':
            if d in rows[r] or d in cols[c] or d in boxes[b]:
                continue
            board[r][c] = d
            rows[r].add(d); cols[c].add(d); boxes[b].add(d)
            if bt(idx + 1):
                return True
            board[r][c] = '.'
            rows[r].discard(d); cols[c].discard(d); boxes[b].discard(d)
        return False
    bt(0)

---

8.4 Key CP Patterns

Problem type	Pruning strategy
Subsets/combinations	start index to avoid reuse
Permutations with dups	Sort + skip if same as prev at same level
N-Queens	Track cols, diagonals in sets
Combination sum	Sort + break on candidate > remaining
Palindrome partition	Check palindrome before recursing

---