What Is Pruning in Backtracking? Don't Finish What Won't Work

For a 15-element array, the permutation search tree has over a trillion nodes. A trillion. You are not visiting all of them. Pruning in backtracking is the technique that makes it practical: recognize a dead end early, cut the branch, and skip the entire subtree below it.

If your backtracking solutions are timing out, pruning is almost certainly the fix.

The Tree You're Trying to Avoid

Every backtracking algorithm builds a decision tree implicitly. Each node is a partial solution. Each edge is a choice. The leaves are complete solutions or failures.

Without pruning, you visit every node. Subset enumeration: O(2^n). Permutations: O(n!). For n = 15, that's 1.3 trillion nodes. For n = 20 with subsets, about one million. One million is manageable. One trillion is a crime against your laptop fan.

The tree exists whether you prune it or not. Pruning decides how much of it you actually visit.

A clown sitting at a coding workstation, captioned: "How it feels while failing to write basic logic through code" Your backtracking solution, pre-pruning, enthusiastically exploring all 1.3 trillion nodes.

For intuition on what these trees look like before pruning, the backtracking algorithm guide walks through the choose-explore-undo cycle. Come back here for the cuts.

Cutting Before You Recurse

Pruning works at an internal node of the decision tree. You check whether any valid solution can possibly descend from here. If not, you stop. Skip the entire subtree and backtrack immediately.

Two main kinds.

Feasibility Pruning: The Constraint Is Already Broken

If your partial solution already violates a rule, adding more choices won't fix it. This is the most common pruning pattern in coding interviews.

N-Queens is the textbook case. You place queens one row at a time. Before placing in column c of row r, check whether any existing queen attacks that square. If yes, skip the column. Because stacking more queens on top of a conflict doesn't resolve the conflict. Shocking, I know.

def is_valid(board, row, col):
    for r in range(row):
        if board[r] == col:
            return False
        if abs(board[r] - col) == abs(r - row):
            return False
    return True

def solve_n_queens(board, row, n, solutions):
    if row == n:
        solutions.append(board[:])
        return
    for col in range(n):
        if is_valid(board, row, col):
            board[row] = col
            solve_n_queens(board, row + 1, n, solutions)
            board[row] = -1

Without that check, you'd place queens everywhere and discover conflicts only at the leaves. That's O(n^n) work. With feasibility pruning, n = 13 drops from roughly 4.5 billion nodes explored to about 16 million. A 99.6% reduction, for the cost of a validity check before each recursion.

Bound Pruning: You Can't Beat the Best

Bound pruning appears in optimization problems. You've found a solution with value V. You're in a branch where, even if every remaining choice goes perfectly, you can't exceed V. Stop. Cut it.

This is the foundation of branch-and-bound algorithms. For standard coding interviews, feasibility pruning is what you'll use most. Knowing bound pruning exists makes your answer to "can we optimize this further?" noticeably sharper.

Combination Sum: Pruning in Practice

LeetCode 39 is where pruning clicks for most people. Find all combinations of candidates that sum to target. Candidates can be reused.

The naive version already checks total > target. That's weak pruning. You're still making the recursive call and discovering the overshoot at the bottom.

The move that changes everything: sort the candidates first. Not bubble sort, to be clear.

Interview meme: "Sort an array of 0s, 1s and 2s. Me: I'll use Bubble Sort. Interviewer: My grandma runs faster than your code." Sorting is good here, actually. Not that kind, but the concept stands.

Sort the candidates. Then use break instead of continue.

def combination_sum(candidates, target):
    candidates.sort()
    results = []

    def backtrack(start, current, remaining):
        if remaining == 0:
            results.append(current[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break  # sorted: every subsequent candidate is also too large
            current.append(candidates[i])
            backtrack(i, current, remaining - candidates[i])
            current.pop()

    backtrack(0, [], target)
    return results

Once candidates[i] > remaining, every candidate from i onward is also too large. You cut the rest of the loop with one instruction instead of recursing into subtrees that can't work.

For candidates [2, 3, 5, 7, 8, 10] and target 7: when you hit 8, you break immediately. You skip 8, 10, and every combination starting with them. Without sorting, you'd recurse into each one and discover the failure only at the bottom.

Diagram showing sorted candidates [2,3,5,7,8,10] with target 7. Candidates 2, 3, 5 recurse normally. 7 finds a solution. At 8, break fires and the subtrees for 8 and 10 are entirely skipped.

Duplicate Handling: A Third Pattern

LeetCode 40 adds duplicates to the mix. Each candidate can only be used once. A different pruning check kicks in:

def combination_sum_two(candidates, target):
    candidates.sort()
    results = []

    def backtrack(start, current, remaining):
        if remaining == 0:
            results.append(current[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break
            if i > start and candidates[i] == candidates[i - 1]:
                continue  # skip duplicate candidates at the same depth level
            current.append(candidates[i])
            backtrack(i + 1, current, remaining - candidates[i])
            current.pop()

    backtrack(0, [], target)
    return results

The i > start and candidates[i] == candidates[i-1] guard skips duplicate candidates at the same level of the tree, preventing identical combinations from appearing twice. Without it, candidates [1, 1, 2] with target 3 produces [1, 2] twice. The sort is what makes this check possible. This pattern shows up everywhere: LeetCode 40, 90 (Subsets II), 47 (Permutations II).

Pruning Doesn't Change Worst-Case Complexity. It Changes Everything Else.

This is the nuance that separates a good interview answer from a strong one.

The worst-case time complexity of backtracking with pruning is the same as without. You can always construct an input where no branches get pruned. The O(2^n) or O(n!) ceiling doesn't change.

What changes is average-case performance on real inputs. For combination sum with a small target and large candidates, most branches die at depth one. For N-Queens, most column placements fail immediately in later rows. Actual runtime on realistic inputs can be orders of magnitude better than the worst case suggests.

When an interviewer asks "what's the time complexity?" after you've added pruning, the honest answer is: still O(2^n) or whatever the base complexity is, but pruning eliminates most of the search tree on typical inputs so the real runtime is far better. That's not hedging. That's correct.

For the full complexity derivation, including why subsets cost O(n·2^n) and permutations cost O(n·n!), see the backtracking time complexity guide.

Why Interviewers Test This

Almost every backtracking problem in a coding interview has a pruning opportunity. Interviewers know this. They're waiting for it. When you implement clean backtracking and pass the base cases, the follow-up is "how do you optimize this?" The answer is pruning. Almost always. Every time.

Common patterns worth knowing cold:

Combination problems with a target sum: sort candidates, break when you exceed the target (LeetCode 39, 40, 216)
N-Queens and Sudoku: check validity before placing, not after
Palindrome partitioning: skip non-palindrome substrings before recursing
Word search on a grid: stop when the current path prefix doesn't match the target word's prefix

The mechanical version: sort if you can, check constraints before recursing, use break instead of continue when the rest of a sorted array can't help. For duplicates: sort first, then skip same-value candidates at the same depth level.

The version interviewers remember is different. Explain the search tree. Sketch which nodes get cut. Walk through why sorting enables break instead of continue. That kind of analysis shows up in feedback as "candidate clearly understood what they were doing, didn't just code it." It's what moves you from a three to a four on the problem-solving dimension.

Explaining pruning out loud under pressure is harder than it sounds. You're reasoning about a tree you can't see, writing code, and narrating at the same time. SpaceComplexity runs voice-based mock interviews with rubric feedback on exactly these dimensions: communication, problem-solving, and code quality. Pruning questions come up regularly, and you'll hear specifically whether your optimization explanation landed.

For recognizing which problems need backtracking at all before you start coding, the backtracking pattern recognition guide covers the signals worth learning.