feasibility pruning
Imagine packing a suitcase by trying items one at a time, and the moment the lid won't close you stop adding things rather than finishing the doomed attempt. Feasibility pruning is that instinct made into an algorithm: as soon as a partial solution already violates a constraint, you reject it and skip every way of completing it. You do not wait until the candidate is finished to discover it was hopeless — you cut it off early.
In the state-space tree, a partial solution is a node, and its possible completions are the subtree beneath it. Feasibility pruning works because of a monotonicity property: for many constraints, once they are violated by a partial solution they stay violated no matter what you add. Two queens that already attack each other will still attack each other after you place more queens; a partial subset that already overshoots a target sum (with only nonnegative items left) can never come back under it. So if the node is infeasible, every leaf in its subtree is infeasible too, and the pruning is sound — you never discard a real solution. Concretely, in the backtracking recursion you insert a check before recursing: if adding this choice breaks a constraint, do not recurse on it; just move to the next candidate.
The savings come from the shape of trees: cutting a node near the root deletes an entire exponential subtree, so even modest pruning can change the practical running time from impossible to instant. This is why backtracking with good feasibility checks routinely solves N-queens or Sudoku that blind enumeration could never touch. The honest caveat: pruning only helps when constraints actually bite early, and in the worst case (few or late-firing constraints) the tree is barely trimmed and you are back to exponential time.
Subset-sum for target 10 from items [6, 8, 3]: building subsets, the partial choice {6, 8} already sums to 14 > 10, and the remaining item 3 is nonnegative, so no extension can drop back to 10. Prune {6, 8} now — and you never test {6, 8} or {6, 8, 3}. Without pruning you would have generated and checked them anyway.
Reject a partial solution the instant it breaks a constraint, and its entire subtree of completions vanishes from the search.
Pruning is only correct when the violated constraint is monotone — it can never be repaired by adding more. Pruning on a constraint that a later choice could fix would silently discard valid solutions, turning a correct search into a wrong one.