Chapter 12: Divide & Conquer and Backtracking

Vol 2: Algorithm Forest Adventure · Station 12

---

Metadata Card

Attribute	Value
Difficulty	(Peak)
Prerequisites	Recursion, Array Operations, Sorting, Search
Keywords	Divide & Conquer Maximum Subarray Inversion Count Backtracking N-Queens Permutations Subsets Pruning

---

Breakthrough · Origins

Divide & Conquer: Three-Step Method

1. Divide: Break the problem into smaller subproblems
2. Conquer: Recursively solve each subproblem
3. Combine: Merge subproblem solutions into the original solution

Maximum Subarray (Divide & Conquer)

def max_subarray(nums):
    def helper(left, right):
        if left == right:
            return nums[left]
        mid = (left + right) // 2
        left_max = helper(left, mid)
        right_max = helper(mid + 1, right)
        # Cross mid sum
        left_sum = float('-inf')
        cur = 0
        for i in range(mid, left - 1, -1):
            cur += nums[i]
            left_sum = max(left_sum, cur)
        right_sum = float('-inf')
        cur = 0
        for i in range(mid + 1, right + 1):
            cur += nums[i]
            right_sum = max(right_sum, cur)
        return max(left_max, right_max, left_sum + right_sum)
    return helper(0, len(nums) - 1)

Inversion Count (Merge Sort Extension)

def count_inversions(nums):
    def merge_and_count(arr, temp, left, right):
        if left >= right:
            return 0
        mid = (left + right) // 2
        count = merge_and_count(arr, temp, left, mid)
        count += merge_and_count(arr, temp, mid + 1, right)
        i, j, k = left, mid + 1, left
        while i <= mid and j <= right:
            if arr[i] <= arr[j]:
                temp[k] = arr[i]; i += 1
            else:
                count += (mid - i + 1)
                temp[k] = arr[j]; j += 1
            k += 1
        while i <= mid: temp[k] = arr[i]; i += 1; k += 1
        while j <= right: temp[k] = arr[j]; j += 1; k += 1
        for i in range(left, right + 1):
            arr[i] = temp[i]
        return count
    return merge_and_count(nums, [0] * len(nums), 0, len(nums) - 1)

Backtracking Template

def backtrack(path, choices):
    if meets_goal(path):
        result.append(path[:])
        return
    for choice in choices:
        if not is_valid(choice, path):
            continue
        path.append(choice)       # Make choice
        backtrack(path, choices)  # Recurse
        path.pop()                # Undo choice

N-Queens

def solve_n_queens(n):
    result = []
    board = [-1] * n

    def is_safe(row, col):
        for r in range(row):
            c = board[r]
            if c == col or abs(r - row) == abs(c - col):
                return False
        return True

    def backtrack(row):
        if row == n:
            result.append(['.' * col + 'Q' + '.' * (n - col - 1) for col in board])
            return
        for col in range(n):
            if is_safe(row, col):
                board[row] = col
                backtrack(row + 1)
                board[row] = -1

    backtrack(0)
    return result

Permutations

def permute(nums):
    result, path = [], []
    used = [False] * len(nums)

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

    backtrack()
    return result

Subsets

def subsets(nums):
    result, path = [], []

    def backtrack(start):
        result.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return result

---

Verification Checklist

• [ ] Can apply the three-step divide & conquer method
• [ ] Can explain divide & conquer for max subarray
• [ ] Can apply the backtracking three elements (choice, constraint, goal)
• [ ] Can hand-write N-Queens
• [ ] Can distinguish permutation (used[]) vs subset (start) backtracking patterns

---

Traveler's Notes

• Divide & Conquer: big problems → small problems → combine
• Backtracking: try all possibilities systematically, undo when stuck
• Pruning is not optimization, it's the soul of backtracking
• Divide & Conquer ≠ Backtracking — D&C has independent subproblems; backtracking explores a state space

---

→ Next Stop Preview

Chapter 13: Dynamic Programming — "The true boss of algorithms."