Backtracking

When to Use

• Problem asks for all combinations / permutations / subsets
• Constraint satisfaction (N-Queens, Sudoku, Word Search)
• Brute force with pruning — explore then undo (backtrack) invalid paths

Signal phrases: "find all ways", "generate all X", "enumerate", "all subsets", "all permutations", "word search", "N-Queens"

---

Universal Recursion Recipe

Four questions to answer before writing any recursive function:

1. Goal: What does f(n) represent / return?
2. Base Case: Smallest trivial version you can solve instantly (e.g., n=0)
3. Recursive Relation: If at index i, how does answer depend on i-1 or i+1?
4. Choices: At current step, what are all valid moves?

---

Core Recursion Patterns

Linear Recursion (one call, "do one thing + delegate the rest")

def factorial(n):
    if n == 0:          # base case
        return 1
    return n * factorial(n - 1)   # one recursive call

# Head recursion: logic AFTER recursive call (processes tail → head)
# Tail recursion: logic BEFORE recursive call (processes head → tail, iterative-style)

Identify: sequence processed one step at a time, state changes by constant (n-1).

Multiple Recursion (Fibonacci / Tree — two+ calls, overlapping subproblems)

def fib(n):
    if n <= 1:
        return n
    left  = fib(n - 1)    # two recursive calls
    right = fib(n - 2)
    return left + right   # combine
# Without memoization: O(2^N). Always add memo for overlapping subproblems → O(N)

Identify: current state depends on multiple previous states, tree-like branching. Leads to DP.

Divide & Conquer (two+ calls, DISJOINT halves)

Unlike Multiple Recursion, subproblems don't overlap — they work on different data.

# Template
def solve(data, left, right):
    if left >= right:
        return handle_base(data[left])   # one element
    mid = left + (right - left) // 2
    left_result  = solve(data, left, mid)
    right_result = solve(data, mid + 1, right)
    return merge(left_result, right_result)   # combine step is the magic

# Python: Merge Sort
def mergeSort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left  = mergeSort(arr[:mid])
    right = mergeSort(arr[mid:])
    return merge(left, right)   # O(N log N) total

Identify: large data, can halve input, sub-problems independent. Classic: Merge Sort, Binary Search, Quick Sort.

---

Grid Exploration Pattern (2D DFS with Backtracking)

# Template for pathfinding in grid: Rat in Maze, Word Search, Number of Islands
DIRECTIONS = [(0,1),(0,-1),(1,0),(-1,0)]   # right, left, down, up

def solveGrid(grid, r, c, visited, path):
    rows, cols = len(grid), len(grid[0])

    # 1. Base case — out of bounds, blocked, or visited
    if r < 0 or c < 0 or r >= rows or c >= cols:
        return
    if grid[r][c] == 0 or visited[r][c]:
        return

    # 2. Goal base case — reached destination
    if r == rows - 1 and c == cols - 1:
        print("Path found:", path)
        return

    # 3. Mark visited (Action)
    visited[r][c] = True

    # 4. Explore all 4 directions
    for dr, dc in DIRECTIONS:
        solveGrid(grid, r + dr, c + dc, visited, path + [(r+dr, c+dc)])

    # 5. Backtrack — unmark so other paths can use this cell
    visited[r][c] = False

# LC 79 — Word Search (mark in-place using '#')
def exist(board, word):
    rows, cols = len(board), len(board[0])
    def dfs(r, c, idx):
        if idx == len(word):
            return True
        if r < 0 or c < 0 or r >= rows or c >= cols or board[r][c] != word[idx]:
            return False
        tmp = board[r][c]
        board[r][c] = '#'   # mark visited in-place
        found = any(dfs(r+dr, c+dc, idx+1) for dr, dc in DIRECTIONS)
        board[r][c] = tmp   # restore (backtrack)
        return found
    return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))

Golden Rule: Always mark visited before recursing, unmark after. Without this, you'll loop forever between two adjacent cells.

---

---

Universal Backtracking Template

def backtrack(start, current_path, result):
    # 1. Base case — valid solution found
    if is_complete(current_path):
        result.append(current_path[:])  # copy, not reference
        return

    for choice in get_choices(start):
        # 2. Make choice
        current_path.append(choice)

        # 3. Recurse
        backtrack(next_start, current_path, result)

        # 4. Undo choice (backtrack)
        current_path.pop()

---

Pattern 1 — Subsets

def subsets(nums):
    result, subset = [], []
    def backtrack(start):
        result.append(subset[:])
        for i in range(start, len(nums)):
            subset.append(nums[i])
            backtrack(i + 1)
            subset.pop()
    backtrack(0)
    return result

---

Pattern 2 — Combinations

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

---

Pattern 3 — Permutations

def permute(nums):
    result = []
    def backtrack(current):
        if len(current) == len(nums):
            result.append(current[:])
            return
        for num in nums:
            if num not in current:
                current.append(num)
                backtrack(current)
                current.pop()
    backtrack([])
    return result

---

Senior Tricks

• Prune early — check constraint before recursing, not after
• Sort first — for problems with duplicates, sorting + skip allows dedup: if i > start and nums[i] == nums[i-1]: continue
• Used set — for permutations, use a boolean used[] array instead of in check (O(1) vs O(N))

---

Problems

---

Notes

<!-- Add your own observations as you solve problems -->