Recursion, Backtracking & Dynamic Programming

01Recursion: the leap of faith

The mental model that makes recursion click: assume the recursive call already works, and just do your one step.

When you write sorted_left = merge_sort(left_half), do NOT trace into it. Treat it like calling a library function some competent colleague wrote — a service you await without reading its source. Your only jobs:

Why the faith is justified: it's mathematical induction wearing a hoodie. If the base case is right, and "smaller-correct ⇒ this-correct," then all sizes are correct. Tracing the call tree in your head is how people get lost; the induction contract is how people get fluent.

def factorial(n):
    if n == 0:            # 1. base case
        return 1
    return n * factorial(n - 1)     # 2. one step, 3. shrinks toward 0

02Backtracking: exhaustive search with an undo button

When: "generate ALL ..." (subsets, permutations, combinations, paths, valid boards) or "does ANY configuration exist." Constraints screaming n ≤ 20 (file 01's decoder ring) confirm it — the answer space is exponential and the interviewer knows.

The idea: build a candidate solution one choice at a time. After exploring a choice fully, undo it and try the next. You're doing DFS over the tree of partial solutions:

subsets of [1,2,3] — at each element: include it, or don't

                         []
                 ┌───────┴───────┐
             include 1        exclude 1
               [1]               []
            ┌───┴───┐         ┌───┴───┐
          [1,2]    [1]       [2]      []
          ┌─┴─┐   ┌─┴─┐    ┌─┴─┐    ┌─┴─┐
      [1,2,3][1,2][1,3][1] [2,3][2] [3]  []      ← 2³ = 8 leaves

The universal template — internalize this shape and most backtracking problems become fill-in-the-blanks:

def backtrack(state, choices):
    if is_complete(state):
        results.append(state.copy())     # ← .copy()! the #1 backtracking bug
        return
    for choice in choices:
        if not is_valid(choice, state):  # prune early — this line is the whole game
            continue
        state.append(choice)             # CHOOSE
        backtrack(state, next_choices)   # EXPLORE  (leap of faith)
        state.pop()                      # UN-CHOOSE — the "undo button"

The three canonical problems

Subsets — at each index: skip or take.

def subsets(nums):
    res, cur = [], []
    def bt(i):
        if i == len(nums):
            res.append(cur[:])
            return
        bt(i + 1)              # exclude nums[i]
        cur.append(nums[i])    # include nums[i]
        bt(i + 1)
        cur.pop()
    bt(0)
    return res

Permutations — at each position: any unused element.

def permutations(nums):
    res, cur, used = [], [], [False] * len(nums)
    def bt():
        if len(cur) == len(nums):
            res.append(cur[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True; cur.append(nums[i])
            bt()
            cur.pop(); used[i] = False
    bt()
    return res

Combination Sum — reuse allowed; avoid duplicate sets by never looking backwards:

def combination_sum(candidates, target):
    res, cur = [], []
    def bt(start, remaining):
        if remaining == 0:
            res.append(cur[:]); return
        if remaining < 0:
            return                          # prune
        for i in range(start, len(candidates)):
            cur.append(candidates[i])
            bt(i, remaining - candidates[i])   # i, not i+1 → may reuse; ≥start → no dup orders
            cur.pop()
    bt(0, target)
    return res

The start index is the idea to narrate: combinations are order-insensitive, so I canonicalize by only choosing forward — each set is generated exactly once, in sorted-position order.

03Dynamic Programming, from first principles

Step 1: watch plain recursion fail

Fibonacci, naively:

def fib(n):
    if n <= 1: return n
    return fib(n - 1) + fib(n - 2)

The tree is huge but contains only n+1 distinct subproblems — recomputed exponentially many times, O(2ⁿ). DP is nothing more than: recursion + never solve the same subproblem twice. Two prerequisites (say these words):

• Overlapping subproblems — the recursion revisits the same states. (Merge sort recurses but never overlaps — so it's divide & conquer, not DP.)
• Optimal substructure — the optimal answer composes from optimal sub-answers.

Step 2: memoization (top-down) — the honest fix

Cache results by input. It IS your recursive solution + a dict. This is caching — the same instinct as putting Redis in front of an idempotent expensive call: pure function of its inputs? Memoize it.

def fib(n, memo={}):
    if n <= 1: return n
    if n not in memo:
        memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

# or, idiomatically:
from functools import lru_cache
@lru_cache(maxsize=None)          # a.k.a. @cache in 3.9+
def fib(n):
    return n if n <= 1 else fib(n - 1) + fib(n - 2)

O(2ⁿ) → O(n): n distinct states × O(1) work each. The general law: DP cost = (number of states) × (work per state).

Step 3: tabulation (bottom-up) — same idea, no recursion

Fill a table from base cases upward, so every dependency is ready before it's needed:

def fib(n):
    if n <= 1: return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

And when today only depends on a fixed window of yesterdays, shrink the table to the window — O(1) space:

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

The 4-step recipe for any DP problem

1. Define the state in words: "dp[i] = the answer for the first i items" / "dp[i][j] = best using items ≤ i with capacity j." If you can't say it in a sentence, stop and redefine.
2. Write the recurrence: dp[i] in terms of smaller states = "what was my last choice?" enumerated.
3. Base cases: the states with trivial answers (empty prefix, zero capacity).
4. Order/extract: memoize (order handles itself) or iterate so dependencies come first; read off the answer state.

04The classic set — five problems, five archetypes

These five are your basis vectors — most interview DP is a linear combination of them:

Climbing Stairs — the hello world (archetype: linear DP)

n stairs, 1 or 2 steps at a time, count the ways. Last move was 1 or 2 ⇒ dp[n] = dp[n-1] + dp[n-2]. It's Fibonacci in a costume — and the costume-lesson generalizes: House Robber (dp[i] = max(dp[i-1], dp[i-2] + a[i])), Decode Ways, Min Cost Climbing.

Coin Change — archetype: unbounded knapsack / min over choices

Fewest coins to make amount. State: dp[a] = fewest coins for amount a. Last coin used was some c ⇒:

def coin_change(coins, amount):
    dp = [0] + [float('inf')] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

O(amount × len(coins)). Why greedy fails (interviewer favorite): coins [1, 3, 4], amount 6 → greedy takes 4+1+1 = 3 coins; optimal is 3+3 = 2. Greedy needs a matroid-like structure; DP doesn't.

Longest Increasing Subsequence — archetype: "ending at i"

State: dp[i] = length of the LIS ending exactly at index i. That "ending at" trick is what makes the recurrence composable:

def lis(nums):
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp, default=0)

O(n²). (There's an O(n log n) patience-sorting version with bisect — name it, derive only if pushed.)

0/1 Knapsack — archetype: two-dimensional choice

Items with (weight, value), capacity W, each item once. State: dp[i][w] = best value using the first i items within capacity w. The recurrence is the eternal binary: skip item i, or take it:

dp[i][w] = max( dp[i-1][w],                          # skip
                dp[i-1][w - wt[i]] + val[i] )        # take (if it fits)

def knapsack(wt, val, W):
    dp = [0] * (W + 1)
    for i in range(len(wt)):
        for w in range(W, wt[i] - 1, -1):   # reversed! see below
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i])
    return dp[W]

The 1-D compression iterates capacity backwards so each item is counted once (forwards would let item i reuse its own updated row = unbounded knapsack — which is exactly the Coin Change loop direction; the two problems differ by a loop order, a genuinely satisfying fact to point out). Costumes: Partition Equal Subset Sum, Target Sum.

Edit Distance — archetype: two sequences

Min insert/delete/replace to turn word1 into word2. State: dp[i][j] = distance between the first i chars and first j chars. Look at the last characters:

if word1[i-1] == word2[j-1]:  dp[i][j] = dp[i-1][j-1]            # free match
else: dp[i][j] = 1 + min(dp[i-1][j],      # delete from word1
                         dp[i][j-1],      # insert into word1
                         dp[i-1][j-1])    # replace
base: dp[i][0] = i, dp[0][j] = j

O(n·m). The grid-over-two-sequences shape also gives you Longest Common Subsequence (== ⇒ 1+diag, else max(up, left)) — LCS and edit distance are the template for every "two strings" DP, and edit distance is literally how diff, spellcheckers, and fuzzy string matching score similarity.

05Recognizing DP — the actual interview skill

The tells, strongest first:

1. Ask-type: "minimum/maximum cost/length/value," "count the number of ways," "can it be done (yes/no over combinations)." Counting-ways is almost a guarantee.
2. Choice-type: at each step a small set of choices (take/skip, which coin, step size), and choices compound.
3. Brute force is exponential, but the "state" is small. You could recurse — and the recursion would revisit states. That revisit is the smell.
4. Greedy feels almost right but you can cook a counterexample (coins [1,3,4] energy).
5. Constraints: n ≤ ~1000–5000 with an expected O(n²)-ish answer often means 2-D DP; "generate all" means backtracking instead — DP counts/optimizes, backtracking enumerates. (If they want the actual list of solutions, no cache can save you — output itself is exponential.)

Deriving live beats pattern-matching from memory — interviewers vary the problem precisely to break memorizers. The five archetypes above are your basis vectors: linear ("last step"), knapsack ("take/skip under budget"), ending-at-i, two-sequence grid, and unbounded (coin) — most interview DP is a linear combination.

Common interview questions

Self-test

1. State the leap-of-faith contract (three obligations) and say why it's just induction.
2. Write the backtracking template from memory. Which two lines are "choose/un-choose," and why is .copy() load-bearing?
3. Generate subsets of [1,2,3] on paper via the include/exclude tree — list the leaves in the order your code would emit them.
4. In Combination Sum, what exactly does passing start (and recursing with i, not i+1) accomplish? Two distinct things.
5. Give the two prerequisites for DP, with one example that has recursion but isn't DP.
6. Convert this to memoized then tabulated: "min cost to reach stair n, paying cost[i] to step from i, moving 1 or 2."
7. Coin change [1,3,4], amount 6 — fill dp[0..6] by hand. Where does greedy diverge?
8. Define the LIS state precisely. Why "ending at i" rather than "within the first i"?
9. Write the knapsack recurrence in both 2-D and 1-D forms. Why must the 1-D capacity loop run backwards?
10. Edit distance "horse" → "ros": set up the first two rows of the table and state what each of the three transitions means.
11. For each, name the technique in ≤ 3 seconds: (a) count paths in a grid with obstacles, (b) all valid IP address splits of a string, (c) min deletions to make two strings equal, (d) can array be partitioned into two equal-sum halves?