Pruning the Search

Pruning means deciding not to explore a subtree because the current partial state already proves that subtree is useless. The branch may violate a constraint, duplicate work already covered by another branch, exceed a bound, or fail to improve the best answer found so far.

The important word is proves. Pruning is safe only when the skipped branch cannot contain a required answer. A fast but unjustified skip changes correctness; a justified skip changes only performance.

The most common pruning checks are local constraints. In N-Queens, do not place a queen in an attacked column or diagonal. In Word Search, do not step outside the grid, revisit the current path, or continue after a character mismatch. In Combination Sum with positive numbers, stop when the remaining target becomes negative.

These checks should happen before the recursive call whenever possible. The earlier you detect an impossible partial state, the larger the subtree you avoid.

Duplicate pruning often starts by sorting. Once equal values are adjacent, a loop can skip a value when the same value has already been tried at the same recursion depth. That removes duplicate result branches without losing unique solutions.

Bound pruning uses arithmetic facts. If you still need k numbers but only m remain, stop. If the smallest possible continuation is already too large, stop. If the largest possible continuation is too small, stop. These bounds are especially valuable for combinations and advanced partitioning problems.

Some problems ask for any valid answer rather than all answers. In those cases, once a valid arrangement is found, recursive calls can return true and stop exploring siblings. Sudoku Solver and Word Search usually use this style.

Optimization backtracking can also prune by comparing a partial score with the current best. If the best possible future cannot beat the best known answer, the branch is not worth exploring. The proof behind that bound is part of the algorithm, not an afterthought.