Recursion and Backtracking Questions

The idea in plain words

A recursive call normally uses the call stack, a fixed-size region of memory holding one frame per active call. Python has no tail-call optimization (the trick where a call that is the very last action of a function reuses its frame), so a deep recursion eventually raises RecursionError (default limit: 1000 frames).

A trampoline avoids deep stacks with two moves:

1. A function does not call the next step; it returns a thunk (a small object that says "call this function with these arguments later"). Here the thunk is the class Bounce.
2. One loop, the trampoline runner, calls the thunk, gets back another thunk, calls that, and so on until a real value comes back. The Python stack never holds more than one step at a time.

Backtracking has one extra difficulty: after a recursive call returns, the function still has work to do (add the two branches together, or undo a choice). That work is not a tail call. The standard fix is continuation-passing style (CPS): each call receives a function k (a continuation, meaning "what to do with my answer") and, instead of returning a value, passes it to k. Now every call is a tail call, so every step can be returned as a thunk. The "rest of the work" that used to wait in stack frames now waits in k closures on the heap. A closure is a function that remembers the variables of the function that created it, and the heap is the general memory area that grows as needed (unlike the fixed-size call stack).

The worked problem is the one from backtracking subset-sum: count the subsets of a list that add up to a target, taking or skipping each value, pruning when the target is unreachable. The same code shape works for N-Queens or Sudoku.

From plain recursion to CPS to a trampoline, on a tiny example

Before the subset search, the same three steps on a sum of 1..n. In total_plain the caller still has + n to do after the recursive call returns. In total_cps that pending + n moves into the continuation (lambda rest: k(rest + n), where lambda writes a small function inline), so the recursive call is the last thing the function does. In total_bounce each step is returned as a Bounce instead of being called, and trampoline runs the chain in a loop:

class Bounce:
    __slots__ = ("fn", "args")

    def __init__(self, fn, *args):
        self.fn, self.args = fn, args


def trampoline(result):
    while isinstance(result, Bounce):
        result = result.fn(*result.args)
    return result


# 1. Plain recursion: after the call returns, the caller still has "+ n" to do.
def total_plain(n):
    if n == 0:
        return 0
    return total_plain(n - 1) + n


# 2. Continuation-passing style: the "+ n" moves into k, and the call is now the last action.
def total_cps(n, k):
    if n == 0:
        return k(0)
    return total_cps(n - 1, lambda rest: k(rest + n))


# 3. Same, but every step is returned as a Bounce so a loop runs it.
def total_bounce(n, k):
    if n == 0:
        return Bounce(k, 0)
    return Bounce(total_bounce, n - 1, lambda rest: Bounce(k, rest + n))


print(total_plain(4))
print(total_cps(4, lambda answer: answer))
print(trampoline(total_bounce(4, lambda answer: answer)))
print(trampoline(total_bounce(50_000, lambda answer: answer)))

Output:

10
10
10
1250025000

The first three lines are the same answer from the three styles; the last line is total_bounce on 50,000 levels, which plain recursion could not do under the default limit.

Code

Applied to the subset count, the plain recursion has the line return explore(i + 1, remaining - vals[i]) + explore(i + 1, remaining). Its CPS form splits that + into two continuations: after_take receives the take-branch count and starts the skip branch, and after_skip receives the skip-branch count and passes taken + skipped to the caller's k. The outermost k is finish, which just hands the final answer to the runner.

import random
import sys
from itertools import combinations


class Bounce:
    """A thunk: 'call fn(*args) later'. Returning one instead of calling it keeps the Python stack flat."""
    __slots__ = ("fn", "args")

    def __init__(self, fn, *args):
        self.fn, self.args = fn, args


def trampoline(result):
    bounces = 0
    while isinstance(result, Bounce):          # the runner: one loop, constant stack depth
        result = result.fn(*result.args)
        bounces += 1
    return result, bounces


def prepare(values):
    vals = sorted(values, reverse=True)
    suffix = [0] * (len(vals) + 1)
    for i in range(len(vals) - 1, -1, -1):
        suffix[i] = suffix[i + 1] + vals[i]
    return vals, suffix


def count_recursive(values, target):
    """Plain recursion: take or skip each value, prune when the target is unreachable."""
    vals, suffix = prepare(values)

    def explore(i, remaining):
        if remaining == 0:
            return 1
        if i == len(vals) or remaining < 0 or suffix[i] < remaining:
            return 0
        return explore(i + 1, remaining - vals[i]) + explore(i + 1, remaining)

    return explore(0, target)


def count_trampolined(values, target):
    """Same search in continuation-passing style: every call receives k, 'what to do with my answer'."""
    vals, suffix = prepare(values)

    def explore(i, remaining, k):
        if remaining == 0:
            return Bounce(k, 1)
        if i == len(vals) or remaining < 0 or suffix[i] < remaining:
            return Bounce(k, 0)

        def after_take(taken):                # the take branch is done; now run the skip branch
            def after_skip(skipped):          # the skip branch is done; add both and pass the sum on to k
                return Bounce(k, taken + skipped)
            return Bounce(explore, i + 1, remaining, after_skip)

        return Bounce(explore, i + 1, remaining - vals[i], after_take)

    def finish(total):                        # the outermost k: hand the final answer to the runner
        return total

    return trampoline(Bounce(explore, 0, target, finish))


def count_explicit_stack(values, target):
    """Explicit stack of pending (i, remaining) states; works because the answers are simply added."""
    vals, suffix = prepare(values)
    stack, total, pops = [(0, target)], 0, 0
    while stack:
        i, remaining = stack.pop()
        pops += 1
        if remaining == 0:
            total += 1
        elif not (i == len(vals) or remaining < 0 or suffix[i] < remaining):
            stack.append((i + 1, remaining))
            stack.append((i + 1, remaining - vals[i]))
    return total, pops


if __name__ == "__main__":
    print("recursion limit:", sys.getrecursionlimit())
    rng = random.Random(11)
    values = [rng.randint(1, 9) for _ in range(14)]
    brute = sum(1 for k in range(15) for c in combinations(values, k) if sum(c) == 20)
    t_count, bounces = count_trampolined(values, 20)
    s_count, pops = count_explicit_stack(values, 20)
    print("brute force", brute, "| recursive", count_recursive(values, 20), "| trampolined", t_count,
          "| explicit stack", s_count)
    print(f"bounces {bounces}, explicit-stack iterations {pops}")

    depth = 100_000                            # one answer exists: take every value; depth = number of values
    deep = [1] * depth
    try:
        count_recursive(deep, depth)
    except RecursionError:
        print("recursive at 100000 values: RecursionError")
    total, bounces = count_trampolined(deep, depth)
    print("trampolined at 100000 values: count", total, "bounces", bounces)

Output:

recursion limit: 1000
brute force 104 | recursive 104 | trampolined 104 | explicit stack 104
bounces 1986, explicit-stack iterations 993
recursive at 100000 values: RecursionError
trampolined at 100000 values: count 1 bounces 400002

The recursive version dies at 100,000 values (a search whose depth equals the number of values); the trampolined one finishes with 400,002 bounces, about four per level. The explicit-stack version appears for comparison and is explained below.

Worked trace

Values [2, 1], target 3 (the only answer is take both). The runner is replaced by a copy that prints each bounce, naming the function being run. For explore the arguments shown are (i, remaining); for a continuation it is the single value it receives:

import tramp
from tramp import Bounce


def traced_trampoline(result):
    bounces = 0
    while isinstance(result, Bounce):
        name = result.fn.__name__
        args = result.args[:2] if name == "explore" else result.args
        bounces += 1
        print(f"bounce {bounces:2d}: {name:10s} args={args}")
        result = result.fn(*result.args)
    return result, bounces


tramp.trampoline = traced_trampoline
print(tramp.count_trampolined([2, 1], 3))

Output:

bounce  1: explore    args=(0, 3)
bounce  2: explore    args=(1, 1)
bounce  3: explore    args=(2, 0)
bounce  4: after_take args=(1,)
bounce  5: explore    args=(2, 1)
bounce  6: after_skip args=(0,)
bounce  7: after_take args=(1,)
bounce  8: explore    args=(1, 3)
bounce  9: after_skip args=(0,)
bounce 10: finish     args=(1,)
(1, 10)

Read it as: bounces 1 to 3 go down the take branch to explore(2, 0), where the target is met and the continuation receives 1. Bounce 4 is after_take for the node at i = 1: it got the take count 1 and starts that node's skip branch, which is bounce 5, explore(2, 1), a dead end (no values left, answer 0). Bounce 6 is that node's after_skip (skip count 0), which passes 1 + 0 on to the root's continuation. Bounce 7 is therefore the root's after_take (take count 1), and it starts the root's skip branch, bounce 8, explore(1, 3): after skipping 2 the remaining values sum to only 1, less than 3, so the answer is 0. Bounce 9 is the root's after_skip (skip count 0), which passes 1 + 0 to finish, bounce 10, and the runner returns (1, 10): count 1 in 10 bounces. Only after_skip adds the two branch counts; after_take just starts the second branch.

Trade-offs against an explicit stack

An explicit stack is a list you manage yourself that holds the pending states, instead of letting the call stack hold them.

Recommendation: for a new piece of code, use the explicit stack; it is faster, shorter and easier to debug. Use a trampoline when the recursive structure must be preserved (mutual recursion, an interpreter, code written in a functional style) in a language without tail-call elimination. In both cases the depth problem is solved by moving it to the heap, which is limited only by memory.

Batched work queues (why recursion does not fit a GPU)

The explicit stack and the trampoline both keep pending states in a data structure; a work queue takes that one step further by processing many states per step. GPU hardware runs groups of threads in lockstep (all executing the same instruction at the same moment, on different data), with a small fixed amount of memory per thread. Deep, data-dependent recursion fits that poorly: threads take different branches and finish at different depths, and each needs its own stack. The shape that fits is the reverse: hold the pending states in a work queue and apply one step to a whole batch of states at once (expand all of them, test all of them, prune all of them). The queue replaces the call stack, and the batch size bounds memory.

The code below shows that scheduling on the CPU for the same problem; it demonstrates the structure, not GPU speed:

import random
from tramp import count_recursive, prepare


def count_batched(values, target, batch):
    """Level-by-level search over arrays of states. Each pop handles up to `batch` states with the same bulk operations."""
    vals, suffix = prepare(values)
    work = [(0, [target])]                        # (level, remaining-values of the states at that level)
    total = peak = batches = 0
    while work:
        i, remainders = work.pop()
        batches += 1
        total += sum(1 for r in remainders if r == 0)
        live = [r for r in remainders if r > 0 and i < len(vals) and suffix[i] >= r]
        if not live:
            continue
        children = [r - vals[i] for r in live if r >= vals[i]] + live      # take branch, then skip branch
        for start in range(0, len(children), batch):
            work.append((i + 1, children[start:start + batch]))
        peak = max(peak, sum(len(b) for _, b in work))
    return total, batches, peak


if __name__ == "__main__":
    rng = random.Random(3)
    for _ in range(300):
        vals = [rng.randint(1, 9) for _ in range(rng.randint(0, 12))]
        target = rng.randint(0, 30)
        assert count_batched(vals, target, batch=rng.choice([1, 2, 5, 64]))[0] == count_recursive(vals, target)
    print("300 random inputs: batched count equals recursive count")

    vals = [rng.randint(1, 30) for _ in range(24)]
    for batch in (10**9, 4096, 256):
        total, batches, peak = count_batched(vals, 150, batch)
        label = "whole level at once" if batch == 10**9 else f"batch size {batch}"
        print(f"{label:20s}: count {total}, batches processed {batches:6d}, peak states stored {peak:8d}")

Output:

300 random inputs: batched count equals recursive count
whole level at once : count 122261, batches processed     25, peak states stored   241125
batch size 4096     : count 122261, batches processed    605, peak states stored    17922
batch size 256      : count 122261, batches processed   9332, peak states stored     1971

All three settings give the same count, 122,261. Processing a whole level at once is the widest possible batch and stores up to 241,125 states; capping the batch at 4,096 or 256 states cuts the peak to 17,922 or 1,971 at the price of more batches (605 and 9,332 against 25), each of which would be one kernel launch on a GPU (one dispatch of the same function over a batch of data). The batch size is the dial between memory and parallel width.

Edge cases and common mistakes

• Calling the next step directly (return explore(...)) instead of returning Bounce(explore, ...) brings back the stack growth.
• Using plain functions as thunks while the real answer can itself be a function: the runner cannot tell them apart, hence a dedicated class.
• Assuming the trampoline saves memory: the chain of continuations is as long as the recursion was deep.
• Capturing a loop variable in a lambda inside a loop: Python looks the variable up when the lambda runs, so all continuations see the last value. Here after_take captures function arguments, which are fixed per call.
• Using this when the language already has tail-call elimination, or when an explicit stack would be simpler.

Running the code

docker run --rm -v "$PWD":/w -w /w python:3.12 sh -c 'python cps_intro.py; python tramp.py; python tramp_trace.py; python tramp_batched.py'

Save the listings as cps_intro.py, tramp.py, tramp_trace.py, tramp_batched.py in one folder. Python 3.12, standard library only.

The idea in plain words

N-Queens asks for the number of ways to place n queens on an n x n board so that no two share a row, a column or a diagonal. Backtracking solves it by placing one queen per row and abandoning (backtracking out of) any partial placement that already has a clash. The search tree is huge, but the board has symmetry: flipping a valid board left to right gives another valid board. So for every solution whose first-row queen sits in the left half, there is a mirror image with its first-row queen in the right half. Count only the left-half cases and double them, and you do about half the work.

The only delicate part is the center column when n is odd. A first-row queen in the center column mirrors to a board that ALSO has its first-row queen in the center, so doubling the center count would count every solution twice. The fix is to apply the same trick one row lower, as explained below.

Brute force and why it is not enough

Trying all n^n placements, or even all n! permutations (one queen per row and column), is hopeless at n = 15. The ordinary backtracking search already prunes every clash early, but the call counts in the table below show it is still exponential: the work grows by a factor of about 3 per extra row at small n and by about 6 per extra row by n = 15 (the last column of the table is the measured ratio). The single mirror removes a constant factor of about 2 (compare the calls_plain and calls_sym columns), which is still worth having at n = 15.

Approach

1. Represent the board with three bitmasks (integers used as sets of bits, one bit per column; column c is bit c, so column 0 is the right-most bit): cols (columns already holding a queen), diag_l and diag_r (squares on the current row attacked along the two diagonals). A queen at column c attacks column c + 1 on the next row along one diagonal and column c - 1 along the other. So when we move down one row, diag_l shifts left by one bit (c to c + 1) and diag_r shifts right by one bit (c to c - 1).
2. In a row, the free squares are full & ~(cols | diag_l | diag_r), where full has all n bits set. Take the lowest set bit with free & -free, place a queen there, recurse, then move on. free & -free works because of two's complement, the way computers store negative integers: -x is the bits of x inverted plus one, which leaves the lowest 1 in place and flips everything above it, so ANDing with x keeps only that lowest 1.
3. Mirror rule for the first row: for each column c in the left half (c < n // 2), count the solutions with the first queen at c and multiply by 2.
4. If n is odd, handle the center column m = n // 2 separately. Mirroring maps column c to n - 1 - c, so a first-row queen at m stays at m and the mirror of such a solution is another solution with its first queen at m. For n >= 3 no solution equals its own mirror: that would need every queen to sit in the center column, and a column holds only one queen. (At n = 1 the single board is its own mirror, which is why n = 1 is handled on its own in the code.) So these solutions come in distinct pairs, and row 0 cannot tell the two members of a pair apart. The row-1 queen can tell them apart: it cannot be in the center column (the row-0 queen already holds it), so it is in the left half or in the right half, and mirroring moves it to the other side. Requiring the row-1 queen to be left of center therefore picks exactly one member of each pair; multiply that count by 2.

The bitmasks on a 4 x 4 board

The program below follows the known 4 x 4 solution with queens in columns 1, 3, 0, 2 and prints the three masks as 4-bit binary strings at the start of each row, then runs the full bit search on n = 4 and n = 5 and mirrors every solution. At each row it also prints what free & -free would pick; the solution does not always use the lowest free square, which is the point of the search.

n = 4
full = (1 << n) - 1                      # 0b1111: one bit per column, column c is bit c (right-most bit = column 0)
cols = diag_l = diag_r = 0
queens = [1, 3, 0, 2]                    # a real solution: row r has its queen in column queens[r]

for row, col in enumerate(queens):
    free = full & ~(cols | diag_l | diag_r)
    print(f"row {row}: cols={cols:04b} diag_l={diag_l:04b} diag_r={diag_r:04b} free={free:04b}")
    bit = free & -free                    # lowest set bit of free
    print(f"       lowest free square: {bit:04b} (column {bit.bit_length() - 1}); the solution uses column {col}")
    bit = 1 << col                        # follow the solution rather than the lowest free square
    cols |= bit
    diag_l = ((diag_l | bit) << 1) & full
    diag_r = (diag_r | bit) >> 1

x = 0b0110
print(f"x = {x:04b}, -x in 4 bits = {-x & 0b1111:04b}, x & -x = {x & -x:04b}")

solutions = []
def go(row, cols, diag_l, diag_r, chosen):
    if row == n:
        solutions.append(tuple(chosen))
        return
    free = full & ~(cols | diag_l | diag_r)
    while free:
        bit = free & -free
        free ^= bit
        go(row + 1, cols | bit, ((diag_l | bit) << 1) & full, (diag_r | bit) >> 1, chosen + [bit.bit_length() - 1])
go(0, 0, 0, 0, [])
mirror = lambda q: tuple(n - 1 - c for c in q)
print("all solutions:", solutions)
print("mirror of each:", [mirror(q) for q in solutions])

n = 5
full = (1 << n) - 1
solutions = []
go(0, 0, 0, 0, [])
print("n=5 solutions with the row-0 queen in the center column (2):")
for q in solutions:
    if q[0] == 2:
        print("  ", q, "mirror", mirror(q), "row-1 column", q[1], "row-1 column of the mirror", mirror(q)[1])
print("any n=5 solution equal to its own mirror:", any(q == mirror(q) for q in solutions))

Output:

row 0: cols=0000 diag_l=0000 diag_r=0000 free=1111
       lowest free square: 0001 (column 0); the solution uses column 1
row 1: cols=0010 diag_l=0100 diag_r=0001 free=1000
       lowest free square: 1000 (column 3); the solution uses column 3
row 2: cols=1010 diag_l=1000 diag_r=0100 free=0001
       lowest free square: 0001 (column 0); the solution uses column 0
row 3: cols=1011 diag_l=0010 diag_r=0010 free=0100
       lowest free square: 0100 (column 2); the solution uses column 2
x = 0110, -x in 4 bits = 1010, x & -x = 0010
all solutions: [(1, 3, 0, 2), (2, 0, 3, 1)]
mirror of each: [(2, 0, 3, 1), (1, 3, 0, 2)]
n=5 solutions with the row-0 queen in the center column (2):
   (2, 0, 3, 1, 4) mirror (2, 4, 1, 3, 0) row-1 column 0 row-1 column of the mirror 4
   (2, 4, 1, 3, 0) mirror (2, 0, 3, 1, 4) row-1 column 4 row-1 column of the mirror 0
any n=5 solution equal to its own mirror: False

Reading it: after the row-0 queen in column 1 (0010), cols is 0010, diag_l is 0100 (shifted left: column 2 is attacked on row 1) and diag_r is 0001 (shifted right: column 0 is attacked). The only free square on row 1 is 1000, column 3. In the row-1 line, cols | diag_l | diag_r is 0111, and free is its complement within full, 1000. The x & -x line shows the trick on 0110: the 4-bit view of -x is 1010, and ANDing keeps only 0010. The last block shows the odd-n pairing for n = 5: the two center-column solutions are mirrors of each other, one has its row-1 queen in column 0 (left of center) and the other in column 4, and no solution equals its own mirror.

Code

solve builds three closures (functions that remember n and full): place counts completions of a partial board, after_first counts completions with a fixed row-0 queen (and optionally a restriction on the row-1 queen), and the third returns the call counter.

def solve(n):
    """Build the counting functions for an n x n board: (after_first, place, get_call_count)."""
    full = (1 << n) - 1
    calls = 0

    def place(cols, diag_l, diag_r, rows_left):
        nonlocal calls
        calls += 1
        if rows_left == 0:
            return 1
        found = 0
        free = full & ~(cols | diag_l | diag_r)
        while free:
            bit = free & -free                    # lowest free square
            free ^= bit
            found += place(cols | bit, ((diag_l | bit) << 1) & full,
                           (diag_r | bit) >> 1, rows_left - 1)
        return found

    def after_first(col, allowed_second=full):
        """Solutions with the row-0 queen in `col`, row-1 queen limited to `allowed_second`."""
        bit = 1 << col
        cols, dl, dr = bit, (bit << 1) & full, bit >> 1
        if allowed_second == full:
            return place(cols, dl, dr, n - 1)
        found = 0
        free = full & ~(cols | dl | dr) & allowed_second
        while free:
            b2 = free & -free
            free ^= b2
            found += place(cols | b2, ((dl | b2) << 1) & full, (dr | b2) >> 1, n - 2)
        return found

    return after_first, place, lambda: calls

def count_with_symmetry(n):
    if n == 1:
        return 1, 0                               # a single square holds the single queen
    after_first, place, get_calls = solve(n)
    half = n // 2
    total = 0
    for col in range(half):                       # row-0 queen in the left half
        total += 2 * after_first(col)             # x2 for the mirrored board
    if n % 2 == 1:                                # row-0 queen in the center column
        center = half
        left_of_center = (1 << center) - 1        # row-1 columns 0..center-1
        total += 2 * after_first(center, left_of_center)
    return total, get_calls()

def count_plain(n):
    after_first, place, get_calls = solve(n)
    total = place(0, 0, 0, n)
    return total, get_calls()

if __name__ == "__main__":
    known = {1: 1, 2: 0, 3: 0, 4: 2, 5: 10, 6: 4, 7: 40, 8: 92, 9: 352, 10: 724,
             11: 2680, 12: 14200, 13: 73712, 14: 365596, 15: 2279184}
    print(" n  solutions  calls_plain  calls_sym  sym_vs_prev_n")
    prev = None
    for n in range(4, 16):
        sym, c_sym = count_with_symmetry(n)
        assert sym == known[n], (n, sym)
        ratio = f"{c_sym / prev:5.1f}x" if prev else "     -"
        prev = c_sym
        if n <= 11:
            plain, c_plain = count_plain(n)
            assert plain == sym
            print(f"{n:2d} {sym:10d} {c_plain:12d} {c_sym:10d}  {ratio}")
        else:
            print(f"{n:2d} {sym:10d} {'':>12} {c_sym:10d}  {ratio}")
    after_first, _, _ = solve(5)
    print("n=5 by row-0 column:", [after_first(c) for c in range(5)])
    print("n=5 center, row-1 left of center only:", after_first(2, 0b00011), "x2 =", 2 * after_first(2, 0b00011))
    tiny = [count_with_symmetry(n)[0] for n in (1, 2, 3)]
    assert tiny == [1, 0, 0]                          # the n == 1 guard and the empty n = 2, 3 boards
    print("n=1, 2, 3:", tiny, "against known", [known[n] for n in (1, 2, 3)])

Run in a python:3.12 container, it prints (the known table holds the published counts, and the plain search is run alongside for n up to 11 as a cross-check; sym_vs_prev_n is calls_sym divided by the previous row's value):

 n  solutions  calls_plain  calls_sym  sym_vs_prev_n
 4          2           17          8       -
 5         10           54         26    3.2x
 6          4          153         76    2.9x
 7         40          552        275    3.6x
 8         92         2057       1028    3.7x
 9        352         8394       4196    4.1x
10        724        35539      17769    4.2x
11       2680       166926      83462    4.7x
12      14200                  428094    5.1x
13      73712                 2337444    5.5x
14     365596                13679276    5.9x
15    2279184                85564535    6.3x
n=5 by row-0 column: [2, 2, 2, 2, 2]
n=5 center, row-1 left of center only: 1 x2 = 2
n=1, 2, 3: [1, 0, 0] against known [1, 0, 0]

Worked trace for n = 5 (odd)

The per-column counts come from the last two lines of the run above: a first-row queen in columns 0, 1, 2, 3, 4 leads to 2, 2, 2, 2, 2 solutions.

Doubling the full center count would have given 2 x 2 = 4 for the center column and a wrong total of 12. That is the double count the question asks you to avoid: the two center-column solutions, (2, 0, 3, 1, 4) and (2, 4, 1, 3, 0) in the mask listing's output, are mirror images of each other, so only one of them has its row-1 queen in the left half.

Complexity

• Time: still exponential, as the call counts show. With the mirror trick the number of recursive calls is about half of the plain search (for n = 11, 83,462 against 166,926). At n = 15 the symmetric version makes 85,564,535 calls. The upper bound is O(n!): row 0 has at most n choices, row 1 at most n - 1 (it cannot reuse the column of row 0), row 2 at most n - 2, and so on. In practice it is far smaller because the masks prune clashes immediately.
• Space: O(n) for the recursion depth (one frame per row, at most 15) plus a few integers per frame. No board array is stored.

Edge cases and common mistakes

• n = 1 is guarded at the top and returns 1: with one row there is no second row to restrict, so the center-column rule does not apply. n = 2 and n = 3 correctly give 0 (the last line of the program output shows 1, 0, 0 for n = 1, 2, 3, and an assertion fails if the n = 1 guard is removed).
• The & full after shifting diag_l left keeps every mask within n bits. In this Python code deleting it changes no count, because free is already ANDed with full, so a stray high bit can never become a free square; the mask still keeps the printed bit strings n digits wide, and in a language with fixed-width integers a left shift can push bits out of the word, so keep it there.
• n = 0 is outside what this code is written for (the question asks for 1 to 15): count_plain(0) returns 1, the single empty arrangement, while count_with_symmetry(0) returns 0.
• Doubling the center column for odd n (the double-count error above).
• Counting "unique up to rotation and reflection" is a different number (n = 8 gives 12 distinct solutions, against the 92 counted here). The simple half-board trick does not give that number; it only speeds up the total.

Counting distinct solutions up to symmetry (canonical form)

A board can be turned into 8 images by 4 rotations, each with or without a reflection. Two boards that are images of each other form one equivalence class (they count as the same solution). Picking the lexicographically smallest of the 8 images (the smallest when the column lists are compared like words in a dictionary) as the representative, called the canonical form, lets you count each class once. Rotating the board 90 degrees sends a queen at (row r, column c) to (row c, column n - 1 - r), which is the formula (c, n - 1 - r) in images. For the 4 x 4 solution (1, 3, 0, 2) the first lines of the output show its images: rotating it gives the same board back and reflecting it gives (2, 0, 3, 1), so this class has only two distinct images, and both 4 x 4 solutions belong to one class (the 4 2 1 line). This approach needs the full set of solutions in memory (2,279,184 tuples at n = 15), against the O(n) extra space of the half-board trick, which is why the trick is preferred for just a count.

def all_solutions(n):
    """Every solution as a tuple: queens[row] = column."""
    out, cols = [], []
    def go(row, used_c, used_d1, used_d2):
        if row == n:
            out.append(tuple(cols))
            return
        for c in range(n):
            if c in used_c or (row - c) in used_d1 or (row + c) in used_d2:
                continue
            cols.append(c)
            go(row + 1, used_c | {c}, used_d1 | {row - c}, used_d2 | {row + c})
            cols.pop()
    go(0, frozenset(), frozenset(), frozenset())
    return out

def images(q):
    """The 8 boards reached by rotating and reflecting a solution."""
    n = len(q)
    cells = [(r, c) for r, c in enumerate(q)]
    result = []
    for flip in (False, True):
        pts = [(r, n - 1 - c) if flip else (r, c) for r, c in cells]
        for _ in range(4):
            pts = [(c, n - 1 - r) for r, c in pts]   # rotate 90 degrees
            board = [0] * n
            for r, c in pts:
                board[r] = c
            result.append(tuple(board))
    return result

def unique_up_to_symmetry(n):
    canonical = set()
    for q in all_solutions(n):
        canonical.add(min(images(q)))               # smallest image names the whole class
    return len(canonical)

q = (1, 3, 0, 2)                                   # row r has its queen in column q[r]
print("images of", q, ":")
for image in sorted(set(images(q))):
    print("  ", image)
for n in range(4, 11):
    print(n, len(all_solutions(n)), unique_up_to_symmetry(n))

It prints (after the images, columns: n, all solutions, distinct up to symmetry):

images of (1, 3, 0, 2) :
   (1, 3, 0, 2)
   (2, 0, 3, 1)
4 2 1
5 10 2
6 4 1
7 40 6
8 92 12
9 352 46
10 724 92

Running the code

python3.12 nqueens_masks.py
python3.12 nqueens_sym.py
python3.12 nqueens_unique.py

Save the three listings under those names. Python 3.12, standard library only. The nqueens_sym.py script takes tens of seconds in plain Python (about 20 seconds in the container used here, so expect it to vary with the machine) because its table reaches the n = 15 line (85,564,535 calls), the largest case it checks.

The idea

Nested lists are a tree: a list is an inner node and an integer is a leaf. Flattening means visiting the leaves left to right. A generator (a function that uses yield to hand back one value at a time and pauses until asked for the next) fits because it produces each integer on demand, so the flat list is never built. The recursive version is natural: for every item, if it is a list, produce everything that list produces (yield from), otherwise yield the integer.

Approach

1. Walk the items in order.
2. A list item: delegate to a recursive call with yield from, which passes the inner generator's values straight out.
3. An integer item: yield it.
4. The iterative version replaces the call stack with your own stack, holding the iterators of the lists currently being walked.

Iterators and StopIteration, in four lines

The iterative version relies on Python's iterator protocol. iter(some_list) returns an iterator, an object that remembers its position in the list; each next(it) returns the following item, and when nothing is left next raises StopIteration, the signal that the sequence is finished. The explicit-stack code below catches that exception to learn that a list is exhausted:

numbers = [7, 8]
it = iter(numbers)          # an iterator remembers its position in the list
print(next(it))
print(next(it))
try:
    next(it)                # nothing left
except StopIteration:
    print("StopIteration: the iterator is exhausted")

Output:

7
8
StopIteration: the iterator is exhausted

The code

from typing import Iterator, List, Union

Nested = Union[int, List["Nested"]]   # a Nested value is an int or a list of Nested values (the type refers to itself)


def flatten(items: List[Nested]) -> Iterator[int]:
    """Recursive generator: yields integers lazily, left to right."""
    for item in items:
        if isinstance(item, list):
            yield from flatten(item)       # hand control to the inner generator
        else:
            yield item


def flatten_iterative(items: List[Nested]) -> Iterator[int]:
    """Same output with an explicit stack of list iterators instead of the call stack."""
    stack = [iter(items)]
    while stack:
        try:
            item = next(stack[-1])
        except StopIteration:
            stack.pop()                    # next() raised StopIteration: this list is exhausted, resume its parent
            continue
        if isinstance(item, list):
            stack.append(iter(item))       # go one level down
        else:
            yield item


data = [1, [2, [3, 4], 5], 6]
print(list(flatten(data)))
print(list(flatten_iterative(data)))

gen = flatten(data)
print(next(gen), next(gen))                # lazy: only two values have been produced so far

edge_cases = [[], [[]], [[], [[]], 7], [[[[1]]]], [0, [-5, [10 ** 20]]]]
for case in edge_cases:
    assert list(flatten(case)) == list(flatten_iterative(case))
    print(case, "->", list(flatten_iterative(case)))

deep = []
for _ in range(5000):
    deep = [deep, 1]                       # 5000 levels of nesting
print(sum(1 for _ in flatten_iterative(deep)))
try:
    sum(1 for _ in flatten(deep))
except RecursionError:
    print("recursive version: RecursionError")

Output:

[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
1 2
[] -> []
[[]] -> []
[[], [[]], 7] -> [7]
[[[[1]]]] -> [1]
[0, [-5, [100000000000000000000]]] -> [0, -5, 100000000000000000000]
5000
recursive version: RecursionError

next(gen) twice returns 1 and 2 and nothing else is computed, which shows the laziness. The 5,000-deep structure at the end, built by repeatedly wrapping, defeats the recursive version (it raises RecursionError, since each level of nesting adds generator frames to the call chain and the default limit is 1000) but not the explicit-stack one.

How the explicit stack works

The stack holds one iterator per open list. Look at the iterator on top: take its next item. If it is a list, push an iterator for it (descend). If it is an integer, yield it. When the top iterator is exhausted, pop it and carry on with its parent, which resumes exactly where it left off, because an iterator remembers its position. This is what the call stack did for you in the recursive version.

Worked trace of [1, [2, [3, 4], 5], 6]

def flatten_iterative_traced(items):
    stack = [iter(items)]
    while stack:
        try:
            item = next(stack[-1])
        except StopIteration:
            stack.pop()
            print(f"  list exhausted, pop -> stack depth {len(stack)}")
            continue
        if isinstance(item, list):
            stack.append(iter(item))
            print(f"  enter {item} -> stack depth {len(stack)}")
        else:
            print(f"  yield {item} (stack depth {len(stack)})")
            yield item


print(list(flatten_iterative_traced([1, [2, [3, 4], 5], 6])))

Output:

  yield 1 (stack depth 1)
  enter [2, [3, 4], 5] -> stack depth 2
  yield 2 (stack depth 2)
  enter [3, 4] -> stack depth 3
  yield 3 (stack depth 3)
  yield 4 (stack depth 3)
  list exhausted, pop -> stack depth 2
  yield 5 (stack depth 2)
  list exhausted, pop -> stack depth 1
  yield 6 (stack depth 1)
  list exhausted, pop -> stack depth 0
[1, 2, 3, 4, 5, 6]

Reading it: the stack depth rises to 3 inside [3, 4], shrinks as lists run out, and the values come out in order 1, 2, 3, 4, 5, 6.

Complexity

• Time: each element of the structure is visited once, so O(N) for N integers and lists in total. The iterative version does O(1) amortised work per element of the structure (each integer or list is pushed, yielded or popped once). That is an average over the whole run, not a promise about each value: the work between two yields can be as long as the nesting is deep, because every level has to be pushed or popped on the way. The listing below counts the loop steps for one integer wrapped in d nested lists, followed by a second integer.

def steps_between_values(depth):
    value = [1]
    for _ in range(depth):
        value = [value]
    stack = [iter([value, 2])]              # the integer 1 sits `depth` + 1 lists down, then comes 2
    steps = []
    while stack and len(steps) < 2:
        count = 0
        while True:
            count += 1
            try:
                item = next(stack[-1])
            except StopIteration:
                stack.pop()
                continue
            if isinstance(item, list):
                stack.append(iter(item))
            else:
                break
        steps.append(count)
    return steps


for depth in (100, 200, 400):
    print(depth, steps_between_values(depth))

Output:

100 [102, 102]
200 [202, 202]
400 [402, 402]

Each of the two values takes d + 2 steps, so the time between values grows with d even though the total work stays O(N).

• The recursive generator pays for depth on every value: a value yielded from depth d is passed up through d yield from levels, so asking for the next value resumes every paused generator on the way down to it. The explicit-stack version resumes one generator per value. The listing counts resumed generator frames per value (sys.setprofile reports a call event each time a paused generator is resumed), for 1000 integers wrapped in depth extra lists:

import sys


def flatten(items):
    for item in items:
        if isinstance(item, list):
            yield from flatten(item)
        else:
            yield item


def flatten_iterative(items):
    stack = [iter(items)]
    while stack:
        try:
            item = next(stack[-1])
        except StopIteration:
            stack.pop()
            continue
        if isinstance(item, list):
            stack.append(iter(item))
        else:
            yield item


def resumes_per_value(func, depth):
    data = list(range(1000))
    for _ in range(depth):
        data = [data]                       # 1000 integers, wrapped in `depth` extra lists
    resumes = 0

    def count_calls(frame, event, arg):
        nonlocal resumes
        if event == "call":                 # also fires each time a paused generator is resumed
            resumes += 1

    gen = func(data)
    next(gen)                               # first value: pay the descent once
    resumes = 0
    sys.setprofile(count_calls)
    for _ in gen:
        pass
    sys.setprofile(None)
    return resumes / 999


for depth in (1, 10, 100):
    print(depth, round(resumes_per_value(flatten, depth), 1), round(resumes_per_value(flatten_iterative, depth), 1))

Output:

1 2.0 1.0
10 11.0 1.0
100 101.1 1.0

The columns are the depth, the recursive version and the explicit-stack version. The recursive form resumes about depth + 1 frames per value and the stack form resumes 1. These counts are one CPython 3.12 measurement.

• Space: O(d) for nesting depth d in both forms (generator frames in one, iterators in the other). The flat list is never built, so memory does not grow with the number of integers.
• Recursion limit: the recursive form fails at roughly the default limit of 1000 nested levels (the 5,000-deep case above). The stack form has no recursion limit; its stack of iterators lives on the heap, and the 5,000-deep case above runs.

Edge cases and common mistakes

• Empty lists anywhere ([], [[]], [[], [[]], 7]) yield nothing for that part and must not stop the walk.
• Negative numbers, zero and very large integers pass through untouched ([0, [-5, [10**20]]]).
• Forgetting yield from and writing flatten(item) alone creates a generator and throws it away, so inner values vanish (on [1, [2, [3, 4], 5], 6] only 1 and 6 come out).
• Writing for x in flatten(item): yield x produces the same values but is wordier than yield from.
• Other iterables: strings are iterable and each character is itself a string, so an isinstance(item, Iterable) test would recurse until RecursionError on "a" (a one-character string yields itself as its only item); testing for list (or for a list/tuple pair) avoids that.
• Mutating the input while a generator is half-consumed changes what the rest of the iteration produces, because the generator reads the live list (appending 9 to [1, 2, 3] after taking the first value makes the remaining values [2, 3, 9]). Copy the input if that matters.

Follow-ups

• Return a flat list instead: list(flatten(x)), which uses O(N) extra memory, the cost the generator avoided.
• Support tuples and other sequences, or a depth limit parameter (flatten only k levels).
• A nested-iterator class with next() and has_next(): has_next() must answer yes or no without consuming a value, so the class runs the explicit-stack loop until it finds the next integer, stores it, and reports True; next() hands out the stored value and fetches the following one.

Running the code

Python 3.12, standard library only.
python3 flatten.py ; python3 flatten_trace.py ; python3 flatten_steps.py ; python3 flatten_resumes.py   (the main listing, the trace, the step counter and the resume counter; the four-line iterator snippet near the top runs on its own)

The difference in plain words

Depth-first search (DFS) is a way of walking a structure that already exists: go as deep as you can along one route, then come back and try the next. Its job is to visit things, and each thing is visited once.

Backtracking uses the same go-deep-then-come-back shape, but the thing being walked is a search space of partial solutions (the set of all the half-built answers you could ever reach) that is built as you go: make a choice, explore what follows, then undo the choice so the next sibling starts from a clean state. Its job is to find or list solutions, and the same item can be used again in different partial solutions.

So backtracking is DFS over an implicit tree of choices (a tree nobody stores: its nodes are partial answers, and each node's children are the ways to extend it by one more choice), plus two extras: an explicit undo step and (usually) pruning, meaning abandoning a branch the moment it cannot succeed.

One graph, both behaviours

A directed graph with a cycle (D -> A) is used for both. The listing contains DFS used for traversal, backtracking that constructs and undoes a partial path, and the two ways to get cycles wrong (a permanent visited mark, and no check at all). A simple path is a route that never repeats a node.

import sys

graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["B", "D"],
    "D": ["A", "E"],     # D -> A closes a cycle; E is a dead end
    "E": [],
}


def dfs_reachable(start):
    """Traversal: visit each node once; 'visited' is never undone."""
    visited, order = set(), []

    def visit(node):
        visited.add(node)
        order.append(node)
        for nxt in graph[node]:
            if nxt not in visited:
                visit(nxt)

    visit(start)
    return order


def all_simple_paths(start, goal):
    """Backtracking: 'on_path' is added on the way down and removed on the way back."""
    paths, path, on_path = [], [start], {start}
    calls = 0

    def explore(node):
        nonlocal calls
        calls += 1
        if node == goal:
            paths.append(path[:])
            return
        for nxt in graph[node]:
            if nxt in on_path:
                continue
            path.append(nxt); on_path.add(nxt)        # choose
            explore(nxt)                              # explore
            path.pop(); on_path.discard(nxt)          # undo

    explore(start)
    return paths, calls


def paths_with_permanent_visited(start, goal):
    """The same search with the traversal habit: visited is never undone."""
    paths, path, visited = [], [start], {start}

    def explore(node):
        if node == goal:
            paths.append(path[:])
            return
        for nxt in graph[node]:
            if nxt in visited:
                continue
            visited.add(nxt); path.append(nxt)
            explore(nxt)
            path.pop()                                # path undone, visited is not

    explore(start)
    return paths


def paths_with_no_cycle_check(start, goal):
    if start == goal:
        return 1
    return sum(paths_with_no_cycle_check(n, goal) for n in graph[start])


print("DFS order from A:", dfs_reachable("A"))
paths, calls = all_simple_paths("A", "E")
print("simple paths A to E:", paths, "calls:", calls)
print("permanent visited:  ", paths_with_permanent_visited("A", "E"))

sys.setrecursionlimit(200)
try:
    paths_with_no_cycle_check("A", "E")
except RecursionError:
    print("no cycle check: RecursionError")


# Growth: k diamonds in a row. Each diamond has two routes, so there are 2**k simple paths.
def diamond_chain(k):
    g = {}
    for i in range(k):
        g[f"j{i}"] = [f"u{i}", f"d{i}"]
        g[f"u{i}"] = [f"j{i + 1}"]
        g[f"d{i}"] = [f"j{i + 1}"]
    g[f"j{k}"] = []
    return g


print("diamonds  dfs_visits  backtracking_calls")
for k in (2, 4, 8, 12):
    graph = diamond_chain(k)
    visited_count = len(dfs_reachable("j0"))
    _, call_count = all_simple_paths("j0", f"j{k}")
    print(f"{k:<9} {visited_count:<11} {call_count}")

Output:

DFS order from A: ['A', 'B', 'D', 'E', 'C']
simple paths A to E: [['A', 'B', 'D', 'E'], ['A', 'C', 'B', 'D', 'E'], ['A', 'C', 'D', 'E']] calls: 10
permanent visited:   [['A', 'B', 'D', 'E']]
no cycle check: RecursionError
diamonds  dfs_visits  backtracking_calls
2         7           13
4         13          61
8         25          1021
12        37          16381

Walking all_simple_paths("A", "E") call by call

The graph: A goes to B and C, B goes to D, C goes to B and D, D goes to A and E. This instrumented copy of the same function prints one line per call (the number is the call count, indentation is the depth, on_path is the set of marked nodes) and a skip line when a neighbour is already marked:

graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["B", "D"],
    "D": ["A", "E"],
    "E": [],
}


def all_simple_paths_traced(start, goal):
    paths, path, on_path = [], [start], {start}
    calls = 0

    def explore(node):
        nonlocal calls
        calls += 1
        note = "  <- goal, record a copy" if node == goal else ""
        print(f"{calls:2}  {'  ' * (len(path) - 1)}at {node}  path={''.join(path)}  on_path={sorted(on_path)}{note}")
        if node == goal:
            paths.append(path[:])
            return
        for nxt in graph[node]:
            if nxt in on_path:
                print(f"    {'  ' * (len(path) - 1)}skip {nxt}: already on the path")
                continue
            path.append(nxt); on_path.add(nxt)
            explore(nxt)
            path.pop(); on_path.discard(nxt)

    explore(start)
    return paths, calls


paths, calls = all_simple_paths_traced("A", "E")
print(["".join(p) for p in paths], "calls:", calls)

Output:

 1  at A  path=A  on_path=['A']
 2    at B  path=AB  on_path=['A', 'B']
 3      at D  path=ABD  on_path=['A', 'B', 'D']
        skip A: already on the path
 4        at E  path=ABDE  on_path=['A', 'B', 'D', 'E']  <- goal, record a copy
 5    at C  path=AC  on_path=['A', 'C']
 6      at B  path=ACB  on_path=['A', 'B', 'C']
 7        at D  path=ACBD  on_path=['A', 'B', 'C', 'D']
          skip A: already on the path
 8          at E  path=ACBDE  on_path=['A', 'B', 'C', 'D', 'E']  <- goal, record a copy
 9      at D  path=ACD  on_path=['A', 'C', 'D']
        skip A: already on the path
10        at E  path=ACDE  on_path=['A', 'C', 'D', 'E']  <- goal, record a copy
['ABDE', 'ACBDE', 'ACDE'] calls: 10

Reading it: calls 1 to 4 go down A, B, D, E. At D the neighbour A is skipped because it is marked, which is the cycle handling, and E is the goal, so a copy of path is recorded. Returning from E, D and B removes their marks (the undo), so by call 5 only A is marked again. That is why call 6 can enter B a second time, this time through C: B is no longer marked. Calls 6 to 8 give the second route ACBDE, and calls 9 and 10 give ACDE. The total is 10 calls, one per line numbered 1 to 10, and 3 recorded paths.

Example 1: DFS used for traversal

dfs_reachable answers "which nodes can be reached from A, and in what order?" It adds a node to visited on entry and never removes it, so the walk touches each node once even though the graph has a cycle. The order is A, B, D, E, C. Cost is O(V + E) time and O(V) space (the visited set plus recursion depth).

Example 2: backtracking that constructs and undoes a partial solution

all_simple_paths answers "list every route from A to E that never repeats a node". The partial solution is path. Each step does choose (append the neighbour and mark it on the path), explore (recurse), undo (pop it and unmark it). It finds three routes: A,B,D,E, A,C,B,D,E and A,C,D,E. Note that B and D appear in several routes, which is only possible because the marks are undone.

The same template with no graph at all is permutation generation: the partial solution is the prefix built so far, and "already used" is a set that is added to and removed from.

How cycle handling differs

• Traversal: mark permanently. A node reached a second time through a different route adds nothing new, so skip it forever. This is what makes DFS linear.
• Backtracking: mark only while the node is on the current path. The question is not "have I ever seen it" but "is it already in the partial solution I am building". The mark is removed on the way back, which is exactly the undo step.
• Using the traversal habit in a path search is a correctness bug. paths_with_permanent_visited finds only one of the three routes, because the first route A,B,D,E marks B, D and E and the marks are never removed: A,C,B,D,E needs B again and A,C,D,E needs D again, so both are blocked.
• Using no check at all never finishes the search. paths_with_no_cycle_check keeps going around A, B, D, A, ..., so the recursion has no bottom. Python stops it by raising RecursionError when the call depth reaches its limit (set to 200 for the demo; the default is 1000); a language with no such limit would run until the stack memory is exhausted.
• The cost of correctness is growth. The last table chains diamonds that each offer two routes (a diamond is a node with two parallel one-step routes that meet again at the next node). DFS visits 3 more nodes per diamond (7, 13, 25 and 37 nodes for 2, 4, 8 and 12 diamonds), while backtracking calls double with each diamond (13, 61, 1,021 and 16,381 calls for the same sizes). Why the calls double: let T(k) be the calls from the first junction through k diamonds. That call makes two child calls (the upper and lower node), each of which makes one call into the rest of the chain, so T(k) = 1 + 2 * (1 + T(k-1)) = 2 * T(k-1) + 3, with T(0) = 1 (the goal alone). That solves to T(k) = 4 * 2^k - 3, which gives 13, 61, 1,021 and 16,381 for k = 2, 4, 8, 12, the numbers printed. DFS with a permanent visited set touches each of the 3k + 1 nodes once, so it grows by 3 per diamond. Exponential growth is why backtracking needs pruning and why a problem like "count the paths" often switches to memoization (caching answers per node) when the graph has no cycles.

Where the search space is itself a tree of choices (subsets, permutations, N-Queens), there is no cycle to detect, because every extra choice makes a strictly bigger partial solution. Only the undo step remains.

Complexity

DFS traversal: O(V + E) time, O(V) space. Backtracking path enumeration: in the worst case it explores every simple path, which is exponential in V (2^k paths for k chained diamonds above); space is O(V) for path, on_path and the recursion depth, plus the output.

Common mistakes

• Treating "visited" as a global flag in a solution-enumeration search, which silently drops valid solutions.
• Forgetting to undo the mark when returning, so later branches see a polluted state.
• Calling a traversal "backtracking" because it returns from recursion. Returning is not backtracking; undoing a choice to try an alternative is.
• Assuming backtracking is always exponential. With strong pruning it can be fast, but its worst case is not bounded by V + E.

Running the code

python3.12 dfs_vs_backtracking.py

Standard library only.

The idea in plain words

A palindrome partitioning splits a string into consecutive pieces so that every piece reads the same forwards and backwards. Backtracking builds the answer one piece at a time: choose a first piece that is a palindrome, recurse on the rest of the string, then undo the choice and try a longer first piece. The pattern is choose, explore, undo.

Every single character is a palindrome, so no branch is ever a dead end, and the number of answers can reach 2^(n-1) (a string of n equal letters has a cut-or-no-cut choice at each of the n-1 gaps). That output size cannot be beaten, so the only thing left to speed up is the palindrome check run at every step.

Approach

1. explore(start) means: the text before index start is already split into palindromes (kept in path).
2. If start equals the length, path is a complete answer. Store a copy (path[:]), because path keeps changing as the search continues.
3. Otherwise try every end index from start up to the last index. If s[start..end] is a palindrome, append it, recurse on end + 1, then pop it.

The palindrome check has two versions:

• On the fly: compare characters from both ends moving inward. Costs up to O(length of the piece) every time, and the same (start, end) pair is re-checked once for every path that reaches start.
• Precomputed table: is_pal[i][j] is True when s[i..j] is a palindrome. A substring s[i..j] is a palindrome when its two end characters match and the inside s[i+1..j-1] is a palindrome. The inside is empty when the substring has length 1 or 2 (j - i < 2 in the code), and an empty inside counts as a palindrome, so for those lengths matching ends are enough. That is a small dynamic programming table: each cell is built from a cell already built. Fill i from the right end downwards so the inner cell exists first. After that, every check in the search is one lookup.

Code

def partition_on_the_fly(s):
    """Check every candidate piece by walking inward from both ends."""
    results, path = [], []
    checks = 0

    def is_palindrome(lo, hi):
        nonlocal checks
        while lo < hi:
            checks += 1
            if s[lo] != s[hi]:
                return False
            lo += 1
            hi -= 1
        return True

    def explore(start):
        if start == len(s):
            results.append(path[:])          # copy: path keeps changing
            return
        for end in range(start, len(s)):
            if is_palindrome(start, end):
                path.append(s[start:end + 1])   # choose
                explore(end + 1)                # explore
                path.pop()                      # undo

    explore(0)
    return results, checks


def partition_with_table(s):
    """Fill is_pal[i][j] once, then every check is a single lookup."""
    n = len(s)
    is_pal = [[False] * n for _ in range(n)]
    fills = 0
    for i in range(n - 1, -1, -1):              # shorter substrings are ready first
        for j in range(i, n):
            fills += 1
            is_pal[i][j] = s[i] == s[j] and (j - i < 2 or is_pal[i + 1][j - 1])

    results, path = [], []

    def explore(start):
        if start == n:
            results.append(path[:])
            return
        for end in range(start, n):
            if is_pal[start][end]:
                path.append(s[start:end + 1])
                explore(end + 1)
                path.pop()

    explore(0)
    return results, fills


if __name__ == "__main__":
    r1, c1 = partition_on_the_fly("aab")
    r2, f2 = partition_with_table("aab")
    print(r1)
    print(r1 == r2)
    for s in ["a" * 12, "a" * 16, "abcdefghijklmnop"]:
        a, checks = partition_on_the_fly(s)
        b, fills = partition_with_table(s)
        assert a == b
        print(f"{s[:6]:>6}.. n={len(s):2d} partitions={len(a):6d} char comparisons on the fly={checks:8d} table cells filled={fills}")

Output:

[['a', 'a', 'b'], ['aa', 'b']]
True
aaaaaa.. n=12 partitions=  2048 char comparisons on the fly=    2724 table cells filled=78
aaaaaa.. n=16 partitions= 32768 char comparisons on the fly=   43682 table cells filled=136
abcdef.. n=16 partitions=     1 char comparisons on the fly=     120 table cells filled=136

Worked trace on "aab"

The table is filled first, one cell at a time, in the order the loops reach them (T marks a palindromic s[i..j]). Then the search runs; each line shows start and the current path, indented by depth. This is the printed output of an instrumented copy of the same code.

s = "aab"
n = len(s)
is_pal = [[False] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
    for j in range(i, n):
        is_pal[i][j] = s[i] == s[j] and (j - i < 2 or is_pal[i + 1][j - 1])
        print(f"fill ({i},{j}) {s[i:j + 1]!r}: ends match={s[i] == s[j]}, "
              f"inside empty={j - i < 2}, result={is_pal[i][j]}")
print("table rows i, columns j:")
for i in range(n):
    print(i, ["T" if is_pal[i][j] else "." for j in range(n)])
path, depth = [], 0

def explore(start):
    print("  " * len(path) + f"start={start} path={path}")
    if start == n:
        print("  " * len(path) + f"-> record {path}")
        return
    for end in range(start, n):
        if is_pal[start][end]:
            path.append(s[start:end + 1]); explore(end + 1); path.pop()
explore(0)

Output:

fill (2,2) 'b': ends match=True, inside empty=True, result=True
fill (1,1) 'a': ends match=True, inside empty=True, result=True
fill (1,2) 'ab': ends match=False, inside empty=True, result=False
fill (0,0) 'a': ends match=True, inside empty=True, result=True
fill (0,1) 'aa': ends match=True, inside empty=True, result=True
fill (0,2) 'aab': ends match=False, inside empty=False, result=False
table rows i, columns j:
0 ['T', 'T', '.']
1 ['.', 'T', '.']
2 ['.', '.', 'T']
start=0 path=[]
  start=1 path=['a']
    start=2 path=['a', 'a']
      start=3 path=['a', 'a', 'b']
      -> record ['a', 'a', 'b']
  start=2 path=['aa']
    start=3 path=['aa', 'b']
    -> record ['aa', 'b']

Read the fill lines top to bottom. Row i = 2 comes first, then i = 1, then i = 0, and inside a row j grows. Cell (0,2), the whole string 'aab', is the only cell that needs an inner cell: its ends a and b differ, so it is False without looking at (1,1). Cell (0,1), 'aa', has matching ends and an empty inside, so it is True at once. The case that uses the table is a longer string such as 'aba': cell (0,2) would read cell (1,1), which is why row 1 must be filled before row 0.

The branch ['aa'] appears because is_pal[0][1] is True, and "aab" as one piece never appears because is_pal[0][2] is False.

Complexity and the trade-off

Let n be the length of the string and P the number of partitions (at most 2^(n-1)).

• Output and search: every recursion node lies on a path to some answer, so there are at most (n + 1) * P nodes (one answer's path passes through up to n + 1 values of start, from 0 to n; for "abc" there is a single answer and 4 nodes, more than n * P = 3), and copying each answer costs O(n). The total is exponential for any version, because the output itself is.
• On the fly: each node scans up to n end positions, and each check costs up to O(n), so the check work per node is O(n^2). Extra space is O(n) for the recursion depth and path.
• With the table: building it costs O(n^2) time and O(n^2) space, and each node then does O(n) work because every check is O(1). The table removes a factor of n from the per-node work and pays n^2 memory for it.
• Measured (comparisons counted, not wall-clock time): on "a" * 16 the on-the-fly version made 43,682 character comparisons against 136 table cells filled. On "abcdefghijklmnop" (no palindrome longer than one character) the on-the-fly version made only 120 comparisons, so the table's 136 fills cost slightly more than they saved.

Recommendation: use the table when the string can contain many palindromic substrings (repeated letters, DNA, long inputs) or when the search is run many times on the same string. Check on the fly when the input is short or has almost no palindromes, because the table is wasted work and O(n^2) memory there.

Edge cases and common mistakes

• Empty string: returns [[]], one partition with zero pieces. Decide with the interviewer whether [] is wanted instead.
• One character, or all characters different: a single partition of single characters.
• Forgetting path.pop() (no undo), or appending path instead of path[:] (every stored answer ends up pointing at the same empty list).
• Filling the table in the wrong order: looping i upward reads is_pal[i+1][j-1] before it has been written.
• Using s[start:end+1] == s[start:end+1][::-1] as the check: correct, but it allocates two strings per check and is still O(length).

Checking it

A short test compares both versions against a brute force that tries every subset of the n-1 cut positions, on 400 random strings over "abc":

import random
from pal import partition_on_the_fly, partition_with_table
def brute(s):
    n=len(s); out=[]
    for mask in range(1<<max(n-1,0)):
        cuts=[0]+[i+1 for i in range(n-1) if mask>>i&1]+[n]
        parts=[s[cuts[i]:cuts[i+1]] for i in range(len(cuts)-1)]
        if all(p==p[::-1] for p in parts): out.append(parts)
    return sorted(out)
random.seed(1)
for _ in range(400):
    s="".join(random.choice("abc") for _ in range(random.randint(1,9)))
    assert sorted(partition_on_the_fly(s)[0])==brute(s)==sorted(partition_with_table(s)[0]),s
print(partition_on_the_fly("")[0], "ok")

[[]] ok

Running the code

docker run --rm -v "$PWD":/w -w /w python:3.12 sh -c 'python pal.py; python pal_trace.py; python pal_test.py'

Save the three listings as pal.py, pal_trace.py, pal_test.py (the test imports pal). Python 3.12, standard library only.