Skip to interview prep
Apexed

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.

What is pruning in backtracking, and what are common pruning strategies — Data structures & algorithms interview question — Apexed