Advanced Recursion & Backtracking

Build one answer at a time, and quit early

List every string of n balanced pairs of parentheses. For n = 3 there are five: ((())), (()()), (())(), ()(()) and ()()(). The obvious plan writes out every string of length 2n made of ( and ) and keeps the balanced ones. For n = 3 that is 64 strings. For n = 14 it is 2²⁸ = 268,435,456 strings, and only 2,674,440 of them survive, about one in a hundred.

Look at what the brute force wastes. A string that starts with ) can never be balanced, and the brute force still builds every one of them: 2²⁷ = 134,217,728 strings, doomed from their first character. Build the string one character at a time instead, and abandon a prefix the moment it cannot be finished. Then the search visits 13,402,696 prefixes for n = 14, and every one of them leads to at least one answer.

That is backtracking: build a candidate one choice at a time, and give up on a partial candidate as soon as it cannot lead to a valid answer. Underneath it is plain recursion walking a tree of choices. This lesson teaches four moves that make such searches correct and fast enough. Each starts with a smell in the problem or in the slow code.

You should be comfortable with Python functions, lists and sets. From Foundation: Arrays & Strings you need output contracts, running summaries, the cost of a slice, and the habit of writing the slow version first. The permutation and combination families have their own lesson, Permutations & Combinations, and board puzzles such as N-Queens and Sudoku live in Constraint Satisfaction. Here you learn the machinery both of them run on.

Move 1: Trust the smaller call

Smell: the answer for your input is easy to build once someone hands you the answer for a smaller input.

The leap of faith

LeetCode 50: Pow(x, n) asks for xⁿ, where x is a float and n is any integer with −2³¹ ≤ n ≤ 2³¹ − 1.

Predict first: the function below is a correct mathematical definition of a power. What does it do for n = -2? For n = 2**31 - 1?

def power_naive(x, n):
    if n == 0:
        return 1.0
    return x * power_naive(x, n - 1)

Every recursive function has to answer three questions:

1. Base case. What is the smallest input you can answer directly?
2. Progress. Does every call move strictly closer to a base case, for every legal input, including negative ones?
3. Combine. If the recursive call on the smaller input returns the right answer, how do you build yours from it?

The third question is the leap of faith. You do not trace the recursive call. You assume it is right for smaller inputs and check only your own combining step. power_naive fails question 2 for negative n, and it shrinks n by only 1 per call, so the chain of calls is as long as n.

Shrink faster. Whatever n is, x ** n equals x ** (n // 2) squared, times one more x when n is odd. Negative exponents flip into positive ones first:

def my_pow(x, n):
    if n < 0:
        return 1 / my_pow(x, -n)      # x to the -n is 1 / (x to the n)
    if n == 0:
        return 1.0
    half = my_pow(x, n // 2)          # trust it: half == x ** (n // 2)
    if n % 2 == 0:
        return half * half
    return half * half * x

Here is what really happens for my_pow(2.0, 10), recorded from a run. Read the table downward for the calls and upward for the returns: frame 5 returns first.

Why it works. Suppose my_pow is right for every exponent smaller than n. Then half is x to the power n // 2, and since n = 2·(n // 2) + (n % 2), squaring half and multiplying by x once more when n is odd gives xⁿ. The base case n = 0 is right, and n // 2 < n for every n ≥ 1, so every chain of calls reaches it. That is a proof by induction, and it is the only "tracing" the function needs. The negative case reuses the positive one.

Cost. n halves on every call, so for n = 2³¹ − 1 the deepest chain is 32 frames, and for n = −2³¹ it is 34: one extra frame for the sign flip, and one more because 2³¹ takes one more halving than 2³¹ − 1. That is O(log |n|) time and O(log |n|) stack space.

Edge cases. my_pow(x, 0) returns 1.0 for every x. x = 0 with a negative n would divide by zero; LeetCode rules that input out.

⚠️ Other languages. In Java or C++, -n overflows for n = −2³¹, because a 32-bit int has no +2³¹. In Java the negation wraps around to −2³¹ again, and the function recurses on a negative number until the stack runs out; in C++ signed overflow is undefined behaviour. Copy n into a 64-bit integer (long in Java, long long in C++) first. Python integers never overflow.

What the call stack is holding

Every call gets its own frame: its own n, its own half, and a note of where to resume in its caller. Frames pile up until a base case returns, then come off in reverse order. This is the real stack at the moment my_pow(2.0, 10) reaches its base case, read with Python's inspect module:

top ->  my_pow(n=0)    about to return 1.0
        my_pow(n=1)    paused at: half = my_pow(x, n // 2)
        my_pow(n=2)    paused at: half = my_pow(x, n // 2)
        my_pow(n=5)    paused at: half = my_pow(x, n // 2)
        my_pow(n=10)   paused at: half = my_pow(x, n // 2)
        (your code)    waiting for the final answer

Two consequences follow.

• Locals are private to their frame. The half in the n = 5 frame and the half in the n = 10 frame are different variables, so a deeper call cannot overwrite yours. The exception is a mutable object that several frames share, and that is Move 2's main trap.
• Depth is space. A recursion d frames deep holds d frames at once, so it uses O(d) memory. Depth is the longest chain of calls, not the total number of calls. my_pow(2.0, 10) makes 5 calls, all on the stack together. The subsets search in Move 2 makes 2,047 calls for 10 numbers, but never has more than 11 on the stack.

The thousand-frame ceiling

CPython refuses to nest more frames than sys.getrecursionlimit() allows: 1,000 by default, counting the frames already on the stack when your function starts, so your own function gets slightly fewer than 1,000 levels before RecursionError. In Java or C++ there is no counter; the limit is the thread's stack size, and running out gives a StackOverflowError in Java or a crash in C++.

Three ways out, best first:

1. Make the recursion shallower. Halving, as in my_pow, gives O(log n) depth.
2. Keep your own stack. Any recursion can become a loop that pushes and pops work on a Python list. Move 4 shows one.
3. Raise the limit with sys.setrecursionlimit(10**6). Since Python 3.11, most pure-Python calls no longer use the C stack; a 1,000,000-deep pure-Python recursion ran fine on CPython 3.11 through 3.14. On CPython 3.9 the same code crashed the whole process with a segmentation fault at 100,000 frames, with no Python error at all. And none of this covers @cache or lru_cache functions: the cache wrapper is C code, so every level of a memoized recursion still uses the C stack (Move 4 has the numbers). Know which interpreter you run on.

Python also does no tail-call elimination: return helper(n - 1, acc * x) still costs one frame per call.

Your turn: the sneaky slice

This function sums a list recursively:

def total(nums):
    if not nums:
        return 0
    return nums[0] + total(nums[1:])

1. Check the three questions. Is it correct?
2. What are its time and extra space?
3. What happens on a list of 1,000 numbers?
4. Rewrite it so the depth is O(log n) and the time is O(n).

def total(nums, lo=0, hi=None):
    if hi is None:
        hi = len(nums)
    if hi - lo == 0:
        return 0
    if hi - lo == 1:
        return nums[lo]
    mid = (lo + hi) // 2
    return total(nums, lo, mid) + total(nums, mid, hi)

Move 2: Walk the decision tree

Smell: the problem says "return all …", and each answer is made of a sequence of small decisions.

In Move 1 each call made one recursive call, so the calls formed a chain. When a call makes two or more, the calls form a tree, and the recursion walks that tree.

Eight subsets, one tree

LeetCode 78: Subsets gives you up to 10 distinct integers and asks for every subset, in any order. [1, 2, 3] has 8.

Predict first: for 10 numbers, how many subsets are there, and how many frames deep does the recursion go?

For a fixed size you could write nested loops: for three numbers, three nested for take in (True, False) loops. But n is an input, and you cannot write n nested loops. A recursive call is one more nested loop, created while the program runs. Counting from 0 to 2ⁿ − 1 in binary also lists every subset, and it is a fine answer to this one problem. It cannot skip anything, though, and Move 3 is all about skipping.

Here is the tree for [1, 2, 3]. Each node is a partial answer, each edge is one decision, and each leaf is a finished subset:

[]
├─ take 1: [1]
│  ├─ take 2: [1, 2]
│  │  ├─ take 3: [1, 2, 3]   stored
│  │  └─ skip 3: [1, 2]      stored
│  └─ skip 2: [1]
│     ├─ take 3: [1, 3]      stored
│     └─ skip 3: [1]         stored
└─ skip 1: []
   ├─ take 2: [2]
   │  ├─ take 3: [2, 3]      stored
   │  └─ skip 3: [2]         stored
   └─ skip 2: []
      ├─ take 3: [3]         stored
      └─ skip 3: []          stored

The recursion visits this tree depth-first. It runs down the leftmost branch to a leaf, backs up one level, tries the other option there, and so on. At any moment the call stack holds exactly one path from the root to the current node, never the whole tree.

This lesson's definition: backtracking is a depth-first search over a tree of partial answers that abandons a partial answer as soon as it cannot lead to a valid one. Subsets never abandons anything, because every leaf is valid. It is backtracking with no pruning, and Move 3 adds the abandoning.

Choose, explore, unchoose

One list, path, holds the partial answer. Every call shares it:

def subsets(nums):
    result = []
    path = []                       # the one partial answer, shared by every call

    def decide(i):                  # decide about nums[i], nums[i+1], ...
        if i == len(nums):          # every element decided: path is a subset
            result.append(path[:])  # store a COPY
            return
        path.append(nums[i])        # choose: take nums[i]
        decide(i + 1)               # explore everything that follows
        path.pop()                  # unchoose: back to how the caller left it
        decide(i + 1)               # explore without nums[i]

    decide(0)
    return result

subsets([1, 2, 3]) returns [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []], the leaves of the tree from left to right. The trace for [1, 2], recorded from a run:

Why it works. Two sentences are true at every call:

1. When decide(i) starts, path holds exactly the elements chosen from nums[0] to nums[i - 1].
2. When decide(i) returns, path is exactly as it was when decide(i) started.

Sentence 2 is what the pop() buys. A leaf never changes path. An inner call appends, calls decide(i + 1), which by sentence 2 hands path back untouched, pops, and calls again. So the skip branch sees exactly what the take branch saw before its append. The pattern has a name: choose, explore, unchoose.

Cost. There are 2ⁿ leaves, and each copies a subset of up to n elements, so the time is O(n·2ⁿ). You cannot do better: each element sits in exactly half of the subsets, so the output alone holds n·2ⁿ⁻¹ numbers. The extra space is O(n), for at most n + 1 frames and a path of length at most n, not counting the output.

Edge cases. subsets([]) returns [[]]: one subset, the empty one, not zero subsets. Inputs with repeated values produce repeated subsets; sorting and skipping equal siblings fixes that, and it is taught in Permutations & Combinations.

The ghost results bug

Predict: change result.append(path[:]) to result.append(path). What does subsets([1, 2, 3]) return now?

A shallow copy is enough for a flat list of numbers. For a list of lists, such as a board, board[:] copies only the outer list and every row stays shared. Store [row[:] for row in board], or turn each row into a string.

Now delete the path.pop() line instead. The skip branch then starts from a path that still holds the element it was supposed to skip, and every later append piles on top:

[[1, 2, 3], [1, 2, 3], [1, 2, 3, 3], [1, 2, 3, 3], [1, 2, 3, 3, 2, 3],
 [1, 2, 3, 3, 2, 3], [1, 2, 3, 3, 2, 3, 3], [1, 2, 3, 3, 2, 3, 3]]

If the choose step changes several things, for example appending to path, marking an element used and adding to a running sum, the unchoose step must undo every one of them, in reverse order.

Plot twist: carry a copy, skip the undo

The undo exists only because every call shares one mutable list. Give each branch its own list and there is nothing to undo:

def subsets_copying(nums):
    result = []

    def decide(i, path):
        if i == len(nums):
            result.append(path)            # this list belongs to this branch alone
            return
        decide(i + 1, path + [nums[i]])    # a brand-new list
        decide(i + 1, path)

    decide(0, [])
    return result

It returns the same eight subsets in the same order. It is still backtracking; the unchoose step is a technique for sharing one mutable object, not what the word means. The price is a copy of up to n elements on every take edge instead of only at the leaves. For subsets that is still O(n·2ⁿ). In a search with many inner nodes and few answers, the shared list with an undo is much cheaper.

Strings, integers and tuples are immutable, so prefix + "(" or total + x already creates a new value. That is why many solutions pass a string down and never undo anything.

⚠️ path += [x] is not path = path + [x]. On a list, += extends the same object in place. This version looks like the copying one, but every call mutates its caller's list:

def subsets_broken(nums):
    result = []

    def decide(i, path):
        if i == len(nums):
            result.append(path)
            return
        decide(i + 1, path)       # skip first this time
        path += [nums[i]]         # looks like a copy; it isn't
        decide(i + 1, path)

    decide(0, [])
    return result

print(subsets_broken([1, 2, 3]))
# [[3, 2, 3, 1, 3, 2, 3], [3, 2, 3, 1, 3, 2, 3], ... the same list eight times]

⚠️ Mutable default arguments. def subsets(self, nums, result=[]) creates that list once, when the function is defined, and every call shares it. On a judge that runs many test cases in one process, the first test passes and the second returns the first test's answers too: [[1], [], [2], []] for [2] after a call with [1]. Create the result list inside the function.

Your turn: XOR totals

LeetCode 1863: Sum of All Subset XOR Totals. The XOR total of a subset is the XOR of its elements, and 0 for the empty subset. Return the sum of the XOR totals over all subsets. [5, 1, 6] gives 28. There are at most 12 numbers.

Write it with the decision tree, but without building a single list. What should travel down the tree instead of path? Predict the result for [1, 3] and for [7].

def subset_xor_sum(nums):
    def total(i, acc):                 # acc = XOR of the elements taken so far
        if i == len(nums):
            return acc
        return total(i + 1, acc ^ nums[i]) + total(i + 1, acc)
    return total(0, 0)

Before you code: count the tree

Backtracking is exhaustive by design, so its cost is the size of the tree it walks. Estimate the size before you write anything:

• Time ≈ nodes visited × work per node, plus answers × the length of each answer.
• Extra space ≈ depth × the size of one frame (including any copy it holds), not counting the output.

Two things stand out. When every inner node has at least two children, the leaves are at least half of all nodes, so counting the leaves gets the order of growth right. And in decision trees like these the depth is the number of decisions, which is small, while the node count is exponential: running out of time is the real danger, not running out of stack. Recursions that step through grid cells or list elements one at a time are the exception, as Move 4 shows.

How big is too big? CPython makes on the order of ten million cheap recursive calls per second on a fast machine: the grid search in Move 4 made 68.8 million calls in about 7 seconds. Judges vary, so treat up to 10⁶ or 10⁷ nodes as comfortable and 10⁸ as trouble.

LeetCode's constraints are the hint. Subsets allows only 10 numbers and Generate Parentheses only 8 pairs because the answers themselves grow exponentially.

Three more rules of thumb:

• The output is a floor. If you must return K answers of length L, no algorithm beats Ω(K·L), because writing them costs that much.
• A good prune changes the base of the exponent. Keep 2 of 10 children at each of d levels and 10ᵈ leaves become 2ᵈ. Real prunes are rarely that uniform, and most leave the worst case exponential. What they change is how much of the tree a real input touches.
• Depth is not the number of answers. 1,024 subsets of 10 numbers never need more than 11 frames.

Your turn: size three trees

Estimate the tree, then say whether a plain search fits:

1. Sum of All Subset XOR Totals with 12 numbers.
2. Return every ordering of a 12-song playlist.
3. Decide whether 15 matchsticks, each assigned to one of 4 sides, can form a square.

Move 3: Prune what can't finish

Smell: most of what the search builds fails a check at the very end.

Back to the parentheses

LeetCode 22: Generate Parentheses asks for every balanced string of n pairs, for 1 ≤ n ≤ 8.

Predict first: for n = 3, how many of the 64 strings of ( and ) are balanced? And what is true of every prefix of a balanced string?

The slow version is the subsets tree again: 2n decisions, each "append (" or "append )", with a balance check at every leaf. For n = 8 it builds all 65,536 strings to keep 1,430, walking 131,071 nodes. The work it repeats is building doomed strings: once a prefix breaks the rule, every string below it fails the same check.

So check the rule at every step and never extend a prefix that breaks it:

def generate_parenthesis(n):
    result = []
    path = []

    def build(opened, closed):
        if closed == n:                  # n closes means n opens too
            result.append("".join(path))
            return
        if opened < n:                   # an open is still available
            path.append("(")
            build(opened + 1, closed)
            path.pop()
        if closed < opened:              # a close has something to match
            path.append(")")
            build(opened, closed + 1)
            path.pop()

    build(0, 0)
    return result

Every node for n = 2, in the order the search visits them:

For n = 3 the whole search is this tree. It has 22 nodes instead of 127, and every leaf is an answer:

""
└─ "("
   ├─ "(("
   │  ├─ "((("
   │  │  └─ "((()"
   │  │     └─ "((())"
   │  │        └─ "((()))"   stored
   │  └─ "(()"
   │     ├─ "(()("
   │     │  └─ "(()()"
   │     │     └─ "(()())"   stored
   │     └─ "(())"
   │        └─ "(())("
   │           └─ "(())()"   stored
   └─ "()"
      └─ "()("
         ├─ "()(("
         │  └─ "()(()"
         │     └─ "()(())"   stored
         └─ "()()"
            └─ "()()("
               └─ "()()()"   stored

Why nothing valid is lost

A prune must pass one test, and this one also passes a second as a bonus.

• It is sound: it never cuts an answer. Every prefix of a balanced string satisfies closed ≤ opened ≤ n, so the two ifs never block a step that some answer takes.
• Bonus: it leaves no dead ends. Many sound prunes, such as the bound in the Boss level below, still leave some. Here, any prefix with closed ≤ opened ≤ n can be finished: append n − opened opens, then n − closed closes. So every node leads to at least one answer.

The payoff: for n = 8 the search visits 6,917 nodes instead of 131,071, and for n = 14 it visits 13,402,696 instead of 536,870,911. Every node is a prefix of some answer, and each answer has 2n + 1 prefixes, so there are at most (2n + 1)·Cₙ nodes, where Cₙ is the number of answers (the Catalan number). The time is O(n·Cₙ) including the O(n) join per answer. The extra space is O(n) for 2n + 1 frames and the path.

A prune is a promise

A prune promises: nothing below this node is an answer. If the promise is false, the search silently returns too few answers, and tests that happen to avoid the bad case will never notice.

Take "list every subset of nums whose sum is target", with the prune "stop as soon as the running sum exceeds the target". It is sound when every number is non-negative, because a sum that can only grow never comes back down. With nums = [5, -3, 1] and target 2, it cuts the branch [5] because 5 > 2, and loses the answer [5, -3]. Without the prune the search returns [[5, -3]]; with it, [].

Before adding a prune, finish the sentence "nothing below here can work, because …". If the "because" needs an assumption, such as non-negative values or sorted input, check that the constraints promise it.

A toolbox of prunes

The sorted break is only as sound as the sort. On unsorted input a later choice can be smaller, and the break silently drops answers.

One more tool is not a prune, but it decides how early prunes fire: ordering. Make the most constrained decision first, such as the item with the fewest places it can go, so that dead ends show up near the root where cutting them saves the most. This fail-first rule chooses which decision to make next. Which value to try first for that decision is a separate knob. When you need just one solution, trying the least constraining value first tends to find it sooner. Constraint Satisfaction develops both for Sudoku and N-Queens.

Your turn: Restore IP Addresses

LeetCode 93: Restore IP Addresses. You get a string of 1 to 20 digits. Return every valid IPv4 address you can make by inserting three dots: four parts, each from 0 to 255, with no leading zeros ("0" is fine, "01" is not). "25525511135" gives ["255.255.11.135", "255.255.111.35"].

Each level of the tree picks the next part, 1 to 3 digits long. Write it with two prunes: a validity check on each part, and a feasibility check that rejects a prefix whose leftover digits cannot fill the remaining parts. How many calls does your search make on a 20-digit string?

def restore_ip_addresses(s):
    result = []
    parts = []

    def place(start):
        left = 4 - len(parts)                 # parts still to place
        rest = len(s) - start                 # digits still unused
        if not (left <= rest <= 3 * left):    # prune: this prefix can't finish
            return
        if left == 0:                         # four parts, no digits left over
            result.append(".".join(parts))
            return
        for end in range(start + 1, min(start + 3, len(s)) + 1):
            piece = s[start:end]
            if (piece[0] == "0" and len(piece) > 1) or int(piece) > 255:
                continue                      # leading zero, or too big
            parts.append(piece)
            place(end)
            parts.pop()

    place(0)
    return result

Boss level: Matchsticks to Square

LeetCode 473: Matchsticks to Square. You get up to 15 matchsticks, each up to 10⁸ long. Using every stick exactly once and breaking none, can you form a square? [1, 1, 2, 2, 2] can (sides 1 + 1, 2, 2 and 2). [3, 3, 3, 3, 4] cannot.

The tree: stick i goes on side 0, 1, 2 or 3. With 15 sticks that is 4¹⁵ = 1,073,741,824 leaves. Two prunes and one ordering rule, each measured on the same hard "no" input, [40, 34, 35, 31, 36, 22, 20, 22, 33, 29, 36, 33, 38, 36, 23], whose side would be 117:

Sorting shortest first instead (with the bound alone) is worse than not sorting at all: 8,254,809 calls.

def makesquare(matchsticks):
    total = sum(matchsticks)
    if total % 4:
        return False
    side = total // 4
    sticks = sorted(matchsticks, reverse=True)   # longest first: fail early
    if sticks[0] > side:
        return False
    sides = [0, 0, 0, 0]

    def place(i):
        if i == len(sticks):
            return True               # no side exceeds `side`, and they total 4 * side
        tried = set()
        for j in range(4):
            if sides[j] + sticks[i] > side:      # bound
                continue
            if sides[j] in tried:                # symmetry
                continue
            tried.add(sides[j])
            sides[j] += sticks[i]
            if place(i + 1):
                return True
            sides[j] -= sticks[i]
        return False

    return place(0)

Why each piece is safe:

• Bound. Sides only grow, so a side that would overflow now overflows in every completion.
• Longest first. This removes nothing; it reorders the decisions. A long stick fits on few sides, so placing the long sticks near the root makes dead ends appear where cutting them saves the most. That is fail-first.
• Symmetry. The four sides are interchangeable. If sides 0 and 2 both hold 36, putting the stick on side 2 leads to the same subtree as putting it on side 0, with two sides renamed. At the start all four sides are 0, so the first stick is tried once instead of four times.
• The base case. When every stick is placed, no side exceeds side and the four add up to 4 × side, so each is exactly side.

The worst case is still exponential. The prunes change how much of the tree a real input touches, and here that is the difference between hopeless and instant.

Move 4: Remember a state, if the past doesn't matter

Smell: the recursion keeps being called with exactly the same arguments.

One grid, three questions

Take an R × C grid with no walls. You start at the top-left corner and want the bottom-right one.

1. How many paths move only right or down? This is LeetCode 62: Unique Paths.
2. How many paths move in all four directions and never visit a cell twice?
3. Can you reach the corner at all?

Predict first: for which questions does "the answer from cell (r, c) onward" depend only on r and c?

The past doesn't matter: memoize

The plain recursion for question 1:

def unique_paths_naive(rows, cols):
    def ways(r, c):                        # paths from (r, c) to the corner
        if r == rows - 1 and c == cols - 1:
            return 1
        if r >= rows or c >= cols:
            return 0
        return ways(r + 1, c) + ways(r, c + 1)
    return ways(0, 0)

It makes 15,392,887 calls on a 13 × 13 grid. The same cell is reached by many different routes, and every arrival recomputes the same answer from scratch. Since that answer depends only on (r, c), compute it once and remember it:

from functools import cache

def unique_paths(rows, cols):
    @cache
    def ways(r, c):                        # paths from (r, c) to the corner
        if r == rows - 1 and c == cols - 1:
            return 1
        if r >= rows or c >= cols:
            return 0
        return ways(r + 1, c) + ways(r, c + 1)
    return ways(0, 0)

Measured on square grids:

On the 13 × 13 grid the body runs once for each of the 169 cells and once for each of the 24 off-grid positions just past the edges. Later calls with the same (r, c) are answered from the cache without running the body. This is memoization, and it is top-down dynamic programming. Dynamic Programming Mastery turns it into tables and evaluation orders.

The one test for when memoization is safe: the result must depend on the arguments alone. A recursion that also reads a shared path or visited set has a hidden argument, and caching on the visible arguments returns stale answers.

Python details that bite:

• functools.cache (Python 3.9+, same as lru_cache(maxsize=None)) uses the arguments as a dictionary key, so they must be hashable. A list argument raises TypeError: unhashable type: 'list'. Pass indices or tuples.
• Define the cached function inside the solving function, as above. Each call then starts with an empty cache that sees the right grid. A cache at module level survives between test cases.
• Memoization removes repeated work, not depth. A chain of 5,000 states is still 5,000 nested calls, and because the @cache wrapper is C code, a raised recursion limit does not save you: with the limit set to a million, a one-line @cache chain failed at depth 5,000 on CPython 3.12 and 3.13 and at 10,000 on 3.14, and crashed 3.11 at 30,000. For deep memoized chains, fill a table bottom-up instead.

The past matters: mark and unmark

Question 2 needs to know which cells the current path uses. That is shared mutable state, so it gets Move 2's choose, explore, unchoose:

def count_simple_paths(rows, cols):
    on_path = [[False] * cols for _ in range(rows)]

    def walk(r, c):
        if not (0 <= r < rows and 0 <= c < cols) or on_path[r][c]:
            return 0
        if (r, c) == (rows - 1, cols - 1):
            return 1
        on_path[r][c] = True                  # choose: this cell is on the path
        total = (walk(r + 1, c) + walk(r - 1, c) +
                 walk(r, c + 1) + walk(r, c - 1))
        on_path[r][c] = False                 # unchoose: later paths may use it
        return total

    return walk(0, 0)

It returns 184 on a 4 × 4 grid, 8,512 on 5 × 5, and 1,262,816 on 6 × 6, the last after 68,830,381 calls. No cache can rescue this. The true state is the current cell plus the set of cells on the path, and there are exponentially many such sets. The unmark is required: a cell used by one path must be free for the next.

Only yes or no: mark once

For question 3 the past doesn't matter, so a cell needs to be explored only once, ever. Mark it and never unmark it:

def reachable(rows, cols):
    seen = [[False] * cols for _ in range(rows)]

    def walk(r, c):
        if not (0 <= r < rows and 0 <= c < cols) or seen[r][c]:
            return False
        if (r, c) == (rows - 1, cols - 1):
            return True
        seen[r][c] = True                     # never undone
        return (walk(r + 1, c) or walk(r - 1, c) or
                walk(r, c + 1) or walk(r, c - 1))

    return walk(0, 0)

Each cell is marked at most once and each marked cell makes four calls, so this is O(R·C). A version that visits every cell of the 6 × 6 grid makes 145 calls. Unmarking here would be a disaster: it turns this into the exponential search of question 2.

The recursion can still be as deep as the number of cells it marks. A recursive search that started in a corner, tried neighbors down, up, right, left, and visited every cell of an open 300 × 300 grid went 90,000 frames deep. The cure is Move 1's second way out, an explicit stack:

def reachable_iterative(rows, cols):
    seen = {(0, 0)}
    stack = [(0, 0)]
    while stack:
        r, c = stack.pop()
        if (r, c) == (rows - 1, cols - 1):
            return True
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in seen:
                seen.add((nr, nc))
                stack.append((nr, nc))
    return False

Graph Traversal covers this family: flood fill, islands, and when to mark a cell.

Your turn: memo, undo, or mark once?

For each problem, pick the move and name the state that matters:

1. LeetCode 139: Word Break: can the string be split into dictionary words?
2. LeetCode 980: Unique Paths III: count the four-direction walks from start to end that pass over every empty square exactly once. The grid has at most 20 cells.
3. LeetCode 200: Number of Islands.

When recursion misbehaves

Most recursion bugs announce themselves with a recognizable symptom:

To watch a recursion, print on entry with indentation. Pass the depth as a parameter, so the indentation follows the stack:

def show_tree(n):
    def build(prefix, opened, closed, depth):
        print("  " * depth + (prefix or '""'))
        if closed == n:
            return
        if opened < n:
            build(prefix + "(", opened + 1, closed, depth + 1)
        if closed < opened:
            build(prefix + ")", opened, closed + 1, depth + 1)
    build("", 0, 0, 0)

show_tree(2)

""
  (
    ((
      (()
        (())
    ()
      ()(
        ()()

The strongest habit is to test against brute force. Backtracking trees for small inputs are tiny, so compare with an obviously correct, slow reference on many random inputs:

import itertools
import random

def subsets_reference(nums):
    return [list(c) for r in range(len(nums) + 1)
            for c in itertools.combinations(nums, r)]

def check(trials=300):
    for _ in range(trials):
        nums = random.sample(range(-10, 11), random.randint(0, 8))
        got = sorted(sorted(s) for s in subsets(nums))
        want = sorted(sorted(s) for s in subsets_reference(nums))
        assert got == want, (nums, got, want)
    print("all matched")

When a case fails, shrink it. The smallest failing input usually has two or three elements, and its whole tree fits on paper.

Final round: no label on the problem

Real problems don't say which move they want. Find the smell, then pick the move.

Challenge 1: Decode String

LeetCode 394: Decode String. k[text] means text repeated k times, and brackets nest. "3[a2[c]]" decodes to "accaccacc", and "2[abc]3[cd]ef" to "abcabccdcdcdef". The input is at most 30 characters and k can have several digits.

1. Which move applies, and why?
2. What should one call return?
3. How deep can the recursion go?

def decode_string(s):
    def decode(i):
        """Decode s[i:] up to the matching ']' or the end; return (text, index)."""
        parts = []
        count = 0
        while i < len(s) and s[i] != "]":
            ch = s[i]
            if ch.isdigit():
                count = count * 10 + int(ch)   # counts can have several digits
                i += 1
            elif ch == "[":
                inner, i = decode(i + 1)       # trust it: decodes up to ']'
                parts.append(inner * count)
                count = 0
                i += 1                         # step past the ']'
            else:
                parts.append(ch)
                i += 1
        return "".join(parts), i

    return decode(0)[0]

Challenge 2: Palindrome Partitioning

LeetCode 131: Palindrome Partitioning. Split a string of at most 16 characters into pieces that are all palindromes, and return every such split. "aab" gives [["a", "a", "b"], ["aa", "b"]].

Which move? What is one decision in the tree? What does the worst case cost?

def partition(s):
    result = []
    pieces = []

    def cut(start):
        if start == len(s):
            result.append(pieces[:])
            return
        for end in range(start + 1, len(s) + 1):
            piece = s[start:end]
            if piece == piece[::-1]:          # prune: palindromic pieces only
                pieces.append(piece)
                cut(end)
                pieces.pop()

    cut(0)
    return result

Challenge 3: Target Sum

LeetCode 494: Target Sum. Put + or - in front of each of up to 20 non-negative numbers (their total is at most 1,000) and count the assignments that reach target. [1, 1, 1, 1, 1] with target 3 gives 5.

Plain backtracking or something else?

from functools import cache

def find_target_sum_ways(nums, target):
    @cache
    def ways(i, running):
        if i == len(nums):
            return 1 if running == target else 0
        return ways(i + 1, running + nums[i]) + ways(i + 1, running - nums[i])
    return ways(0, 0)

Cheat sheet

Before moving on, take Generate Parentheses or Restore IP Addresses and explain it aloud from a blank editor: what one decision is, what the tree looks like, what the shared state holds when a call starts and when it returns, which prune fires and why it can never cut an answer, and how many nodes the search visits. If you can do that, the permutation, combination and board-puzzle lessons are the same machine with different decisions.

Next: Permutations & Combinations for orderings, selections and duplicate handling, Constraint Satisfaction for N-Queens, Sudoku and Word Search, and Dynamic Programming Mastery for what memoization grows into.