Pruning (Early Stopping in Search Trees)

Pruning means stopping a recursive branch as soon as you know it cannot lead to a valid answer. You explore fewer nodes and avoid time-limit errors on large search spaces.

Why this shows up in the real world

Puzzle solvers, scheduling tools, and interview backtracking all hit the same wall: brute force is too slow. Pruning is the standard way to keep DFS-style search practical.

Core idea (explained for students)

At each recursive step, ask: can this partial state still succeed? If not, return immediately instead of going deeper.

Classic checks:

• Partial sum already exceeds the target (subset sum / combination sum).
• Remaining budget cannot fit the smallest items left.
• A constraint is already violated (no two adjacent picks, invalid board placement).

Place the check at the start of the function, before you make the next choice.

Try this in Python

def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    candidates.sort()
    res: list[list[int]] = []

    def dfs(start: int, remain: int, path: list[int]) -> None:
        if remain == 0:
            res.append(path.copy())
            return
        if remain < 0:
            return
        for i in range(start, len(candidates)):
            x = candidates[i]
            if x > remain:
                break
            path.append(x)
            dfs(i, remain - x, path)
            path.pop()

    dfs(0, target, [])
    return res


print(combination_sum([2, 3, 6, 7], 7))

Common mistakes

• Checking the prune condition after recursing—too late; you already paid for useless work.
• Pruning that is too aggressive and throws away valid solutions (always test with a small counterexample).
• Forgetting to undo state when you backtrack after a failed branch.

Key takeaways

• Pruning does not change what you search for—it cuts branches that cannot help.
• Sort inputs when break on x > remain is part of your rule.
• Draw a tiny recursion tree and mark which nodes pruning skips.