10. Recursion & Backtracking

What Interviewers Test Here

• Converting a problem into recursive choices
• Backtracking template: make choice → recurse → undo choice
• Pruning to avoid exploring dead branches early
• Snapshot results (path[:]) before returning

# --- Backtracking template ---
def backtrack(result, path, choices, start):
    if is_complete(path):
        result.append(path[:])   # snapshot
        return
    for i in range(start, len(choices)):
        if not is_valid(path, choices[i]):
            continue
        path.append(choices[i])
        backtrack(result, path, choices, i + 1)
        path.pop()               # undo choice

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

# --- All permutations ---
def permutations(nums: list[int]) -> list[list[int]]:
    result, path = [], []
    used = [False] * len(nums)
    def bt():
        if len(path) == len(nums):
            result.append(path[:]); return
        for i, x in enumerate(nums):
            if used[i]: continue
            used[i] = True; path.append(x)
            bt()
            used[i] = False; path.pop()
    bt()
    return result

---

Conceptual Q&A

Q1: "Generate all valid combinations of n pairs of parentheses."

Walkthrough:

"I build the string character by character. At each step I can add ( or ). The constraints:

• I can add ( if I've used fewer than n open brackets: open < n
• I can add ) if it won't create an invalid prefix: close < open

These two conditions are my pruning rules. When open == close == n, I have a valid combination.

No explicit 'undo' needed since strings are immutable — passing current + '(' creates a new string."

def generate_parentheses(n: int) -> list[str]:
    result = []
    def bt(current: str, open: int, close: int):
        if len(current) == 2 * n:
            result.append(current)
            return
        if open < n:
            bt(current + '(', open + 1, close)
        if close < open:
            bt(current + ')', open, close + 1)
    bt('', 0, 0)
    return result

# n=3: ["((()))","(()())","(())()","()(())","()()()"]

---

Q2: "Given a list of numbers, find all subsets that sum to a target (combination sum)."

Walkthrough:

"This is a backtracking problem. At each position I decide: include this number or skip it. Since the same number can be reused, I don't advance start when including.

Pruning: if candidates[i] > remaining, stop (sorted array, so all subsequent are also too large).

Steps:

1. Sort candidates (enables pruning)
2. Recurse with index start, remaining decreasing as I add numbers
3. When remaining == 0, add snapshot to result
4. When remaining < 0 or candidates[start] > remaining, return"

def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    candidates.sort()
    result, path = [], []

    def bt(start: int, remaining: int):
        if remaining == 0:
            result.append(path[:]); return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break   # pruning: rest are larger, no need to check
            path.append(candidates[i])
            bt(i, remaining - candidates[i])   # i (not i+1): allow reuse
            path.pop()

    bt(0, target)
    return result

---