Pruning Techniques

Pruning in backtracking means skipping branches that cannot produce a valid or optimal solution. It reduces the search space and often turns an exponential search into a tractable one.

When to Prune

• Constraint violation: The current path already breaks a hard constraint (e.g. sum exceeds target, duplicate used).
• Impossible to reach goal: Even with the best possible continuation, the goal cannot be met (e.g. remaining elements cannot fill the rest of the partition).
• Dominance: Some partial solution is provably worse than another you already have (in optimization).

Early Exit on Constraint

As soon as the current state is invalid, return without recursing further.

JavaCopy
void dfs(int[] nums, int i, int sum, int target, ...) {
    if (sum > target) return;  // prune: already over
    if (i == nums.length) {
        if (sum == target) record();
        return;
    }
    // ...
}

Pruning by Remaining Capacity

In partition or subset-sum style problems, if the sum of the remaining elements is less than what you still need, you can’t reach the target — prune.

JavaCopy
int remaining = 0;
for (int j = i; j < nums.length; j++) remaining += nums[j];
if (sum + remaining < target) return;

Pruning in Combination Sum

When building combinations that sum to target, sort the array and prune when sum + nums[i] > target for the rest of the branch (no need to try larger indices if they’re all ≥ current).

Order of Pruning

Apply the cheapest checks first (e.g. sum > target) before more expensive ones (e.g. computing remaining sum). Combine multiple pruning conditions when possible.

Summary

Prune when the current path violates a constraint, when the goal is unreachable with the remaining choices, or when the partial solution is dominated. Pruning keeps backtracking efficient and is essential for harder problems.