Backtracking and Safe Pruning Rules

Backtracking problems all look the same from a distance: build a candidate one decision at a time, and when the partial candidate can’t become an answer, step back and try the next option. Subsets, permutations, Combination Sum, N-Queens, Word Search and Generate Parentheses are the usual interview suspects.

The part that separates a working answer from a strong one is pruning. A prune cuts off a whole subtree of the search without visiting it. Done right, it turns a search that times out into one that finishes instantly. Done wrong, it quietly drops valid answers, and because small test cases often still pass, nobody notices until the hidden tests run. This note treats every prune as a small claim you have to justify, and shows what happens when the justification is missing.

Choose, explore, unchoose

The core loop has three moves. You choose an option by mutating shared state (append to a path, mark a cell, place a queen). You explore by recursing with that choice in place. You unchoose by reversing the mutation exactly, so the next sibling starts from the same state you did.

Here’s Combination Sum: given distinct positive integers and a target, return every combination that sums to the target, where each number may be reused. The code counts recursive calls so you can see what pruning buys.

def combination_sum(candidates, target, prune=True):
    candidates = sorted(candidates)
    result, path = [], []
    calls = 0

    def dfs(start, remaining):
        nonlocal calls
        calls += 1
        if remaining == 0:
            result.append(path[:])          # copy: path keeps changing
            return
        if remaining < 0:
            return
        for i in range(start, len(candidates)):
            c = candidates[i]
            if prune and c > remaining:     # sorted + positive: every later c is bigger too
                break
            path.append(c)                  # choose
            dfs(i, remaining - c)           # explore (i, not i + 1: reuse allowed)
            path.pop()                      # unchoose

    dfs(0, target)
    return result, calls

Two details carry a lot of weight. Passing start and looping from it means you only ever pick candidates at or after the last one you picked, so [2, 2, 3] is generated once and [3, 2, 2] never appears. Recursing with i rather than i + 1 is what allows reuse. Swap it for i + 1 and you get the “each number once” variant.

Running it on three inputs, with and without the prune, gives identical results and very different amounts of work:

[2, 3, 6, 7] target=7: [[2, 2, 3], [7]]
  calls without prune=28, with prune=10
[2, 3, 5] target=8: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]
  calls without prune=23, with prune=13
[3, 5, 7, 9, 11, 13] target=30: 25 combinations
  calls without prune=610, with prune=220

On the third input the pruned search makes about a third of the calls. The gap widens as the target grows, because each avoided call would have spawned its own subtree.

What makes a prune safe

Look at the line if prune and c > remaining: break. It’s a break, not a continue, which means it skips the current candidate and every candidate after it. That’s a strong claim, so say out loud why it holds:

1. The candidates are sorted, so every candidate after c is at least c.
2. Every candidate is positive, so adding more numbers can only increase the sum.
3. If c alone overshoots remaining, then any later candidate overshoots too, and nothing added afterwards can bring the sum back down.

All three facts are needed. Drop the sort and break becomes wrong (a smaller candidate might come later), so you’d have to downgrade to continue. Drop positivity and the whole argument falls apart.

That second case is the trap interviewers like to set with a follow-up: “What if the array can contain negative numbers?” Here’s a subset-sum search with the same style of prune, given [-4, -2, 3, 5] and a target of -6:

def subsets_with_sum(nums, target, prune):
    nums = sorted(nums)
    out, path = [], []
    def dfs(start, total):
        if total == target and path:
            out.append(path[:])
        for i in range(start, len(nums)):
            if prune and total + nums[i] > target:
                break                       # assumes adding more can only grow the total
            path.append(nums[i])
            dfs(i + 1, total + nums[i])
            path.pop()
    dfs(0, 0)
    return out

nums = [-4, -2, 3, 5]
print("no prune:  ", subsets_with_sum(nums, -6, prune=False))
print("bad prune: ", subsets_with_sum(nums, -6, prune=True))

no prune:   [[-4, -2]]
bad prune:  []

At the root, 0 + (-4) is -4, which is greater than -6, so the prune fires and the search ends before it ever tries adding -2. The code doesn’t crash or warn. It just returns nothing. That’s the failure mode of an unjustified prune: wrong answers that look plausible.

Gotcha

If you add a prune during an interview, state the property it relies on (“this is safe because the input is sorted and all values are positive”). Interviewers often probe exactly that property next, and having already named it shows you know where the boundary is.

Pruning duplicates without losing answers

A second kind of prune removes branches that would produce answers you already have. Combination Sum II allows duplicate values in the input but uses each element at most once, and wants each distinct combination once. With [10, 1, 2, 7, 6, 1, 5] and target 8, a naive search finds [1, 2, 5] twice, once with each 1.

The standard fix sorts the input and adds one check at the top of the loop: skip candidates[i] if it equals candidates[i - 1] and i > start. The important part is i > start. Many candidates write i > 0 instead, and here’s what each version returns:

no skip:    [[1, 1, 6], [1, 2, 5], [1, 7], [1, 2, 5], [1, 7], [2, 6]]
i > start:  [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
i > 0:      [[1, 2, 5], [1, 7], [2, 6]]

The i > 0 version loses [1, 1, 6]. The reason is about which level of the tree you’re at. Within one loop, every iteration picks a different value for the same position in the combination. Picking the first 1 or the second 1 for that position leads to identical subtrees, so skipping the second is safe. But when you recurse after choosing the first 1, the loop starts at the second 1, and now picking it means using a second copy in the next position, which is a genuinely different combination. i > start skips repeats among siblings only; i > 0 also blocks that legitimate deeper choice.

The bug that empties every result

One mistake shows up in this pattern more than any other. You store path instead of a copy of it:

if remaining == 0:
    result.append(path)             # bug: same list object every time
    return

On [2, 3, 6, 7] with target 7 that version prints [[], []]. Both entries reference the same list object, and by the time the search finishes every append has been undone by a matching pop. The fix is path[:] (or list(path) in Python, [...path] in JavaScript). Count of results right, contents empty: that symptom always means aliasing.

The same discipline applies to every piece of mutable state. If you mark a grid cell as visited in Word Search, you must unmark it after the recursive call returns, or a later path that legitimately needs that cell will find it blocked.

Cost: what to say about complexity

Backtracking is exponential in the worst case, and interviewers don’t expect a tight closed form for every variant. They do expect you to reason about the shape of the tree:

• Subsets of n items: 2^n leaves, and copying each subset costs up to n, so O(n · 2^n) time.
• Permutations: n! leaves, O(n · n!) time including copies.
• Combination Sum: the depth is at most target / min(candidates) and each level branches at most n ways, so a loose bound is O(n^(T/m + 1)) where T is the target and m the smallest candidate.

Space, excluding the output, is the recursion depth plus the path: O(n) for subsets and permutations, O(T/m) for Combination Sum. Pruning rarely improves the worst-case bound. What it changes is how much of the tree you actually visit on realistic inputs, which is why the call counts above matter more in practice than the big-O.

Interview practice: Generate Parentheses

Given n, return every string of n pairs of balanced parentheses. A brute-force approach generates all 2^(2n) strings of ( and ) and filters the valid ones. What prunes make the search generate only valid strings, and why is each one safe?

Answer

Track how many openers and closers you’ve placed. Two rules:

• Add ( only while opened < n. Once you’ve used n openers, any string with another one has more than n and can’t be part of a valid answer.
• Add ) only while closed < opened. A closer with no unmatched opener before it makes the prefix invalid, and no suffix can repair a prefix that has already gone negative.

Both rules reject a prefix only when no completion of it is valid, which is exactly the safety condition. And they’re complete: any prefix that passes both checks can still be finished (close every open bracket after using the remaining openers), so the search never wanders into a dead end.

def generate_parentheses(n):
    out, path = [], []
    def dfs(opened, closed):
        if len(path) == 2 * n:
            out.append("".join(path))
            return
        if opened < n:
            path.append("(")
            dfs(opened + 1, closed)
            path.pop()
        if closed < opened:
            path.append(")")
            dfs(opened, closed + 1)
            path.pop()
    dfs(0, 0)
    return out

With a call counter added, the real numbers are:

n=3: ['((()))', '(()())', '(())()', '()(())', '()()()'], calls=22, unpruned leaves=64
n=4: 14 strings, calls=64, unpruned leaves=256
n=8: 1430 strings, calls=6917, unpruned leaves=65536

For n = 8 the pruned search makes 6,917 calls in total, while brute force would build 65,536 complete strings before filtering. The output counts are the Catalan numbers (5, 14, 1430), and since every leaf is a valid answer, the work is proportional to the output size times n. Practise it on Generate Parentheses, then try Combination Sum and Word Search with the same “justify every prune” habit.

Keep going

• Data Structures and Algorithms interview questions
• DSA multiple-choice questions
• Dynamic Programming and State Definition, for when the same subproblems keep reappearing in the tree
• Algorithm Space Complexity and Auxiliary Storage, on counting recursion depth
• MIT 6.006 Introduction to Algorithms (Spring 2020)