Backtracking

🧠 Spot It

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

Rule of thumb: if the problem says "find all ways" or "generate all X", think backtracking.

---

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 -->