Pruning: making exponential searches fast enough

Backtracking Mid-level Python 3.13+ Reviewed By Best Latest Apps

Pick the fix

Prices are sorted ascending, and adding prices[i] already passes the goal. What should the loop do?

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A Break: every later price is at least as big

Right: sorting turns one overshoot into a stop for the whole loop.

Ordering the input is what makes the stronger prune safe, and it often matters more than any micro-optimisation.

Why not the others?
  • B Continue to the next price. Correct, but it checks prices that must also overshoot.
  • C Return the current count as the final answer. Other branches higher in the tree may still find hits.

30-second answer

Pruning cuts branches that cannot produce an answer. Common kinds: bound checks (the total already passes the goal), feasibility checks (not enough items left), ordering (sort so the first overshoot ends the loop), duplicate skipping (equal values at the same depth) and constraint sets (used columns and diagonals). The worst case stays exponential, but typical inputs shrink dramatically.

Practise saying it · 45 s. No recording, just a timer

Explain pruning in backtracking.

Say your answer out loud, then check which of these points you covered:

  • Bounds and feasibility
  • Sort to break early
  • Worst case unchanged

Deep dive

Sorting ascending turns 'this item overshoots' into 'every later item overshoots', so you can break, not just continue.

Trying the most constrained choice first finds dead ends sooner.

Memoising a branch's result turns backtracking into DP when states repeat.

Common mistakes

  • Claiming pruning changes the worst-case complexity.
  • Pruning on assumptions the input does not guarantee, such as positive values.

Senior take & follow-ups

Name one prune per question and say why it is safe.

Follow-up questions

Think of your answer first, then open the hint.

  1. How do you measure a prune's effect?

    Show hint

    Count recursive calls with and without it on realistic inputs.

  2. What is 'most constrained first'?

    Show hint

    Choose the slot with the fewest legal options next, as Sudoku solvers do.

What each operation costs: Depth First Search

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.