Backtracking Target: 15s
Pruning transforms exponential backtracking into something practical. Always ask: can I reject this branch without exploring it?
PRUNING STRATEGIES
──────────────────
1. CONSTRAINT PRUNING — skip invalid choices early
if not is_valid(choice): continue
Example: N-Queens skip attacked cells
2. SORTED + SKIP DUPLICATES
nums.sort()
if i > start and nums[i] == nums[i-1]: continue
Example: Combination Sum II, Subsets II
3. REMAINING SUM CHECK — can we still reach target?
if remaining < 0: return # overshot
if remaining < min_choice: return # can't reach
4. BOUND CHECK — is best possible better than known?
if optimistic_bound <= best_so_far: return
Example: branch and bound
5. SYMMETRY BREAKING — avoid symmetric solutions
Fix first element, only explore from there
Example: N-Queens first queen in left half
ORDER: sort choices so pruning triggers earlier.
Try most constrained variable first (MRV).Type it from memory. Go.