81. What is pruning in backtracking, and what are common pruning strategies?
MediumRecursion & backtracking
Technical
Show model answer
Backtracking explores a tree of partial solutions. Pruning cuts a subtree as soon as you can prove it cannot lead to a valid or better solution, which can turn an infeasible search into a fast one even though the worst case bound stays exponential.
Common strategies: feasibility checks before recursing (N-Queens attack sets, Sudoku row/column/box sets), bounds on the remaining budget (a sorted subset sum breaks once a candidate exceeds the remaining target), branch and bound (skip a branch whose optimistic estimate cannot beat the best found so far), choosing the most constrained variable first, and deduplication by sorting and skipping equal choices at the same level.