Here is the N-Queens problem: place 8 queens on an 8×8 board so that no two queens attack each other. A brute-force approach tries every possible placement — that is 8 positions for each of 8 rows, or 8⁸ = 16.7 million combinations.

A backtracking approach with pruning checks constraints before placing each queen. If a column or diagonal is already occupied, it skips that position entirely — it never even enters the subtree.

Now you are the pruning function. The problem: find combinations from 235 that sum to 7.

At each node, you see the current path and the remaining sum. Your job: decide whether to explore this branch (the remaining sum can still reach 0) or prune it (it is a dead end — no combination of candidates can fill the gap).

16.7 million vs 15 thousand. That is not a percentage improvement — it is a thousand-fold reduction. And the difference comes down to one question asked at the right time: “Is this choice even valid?”

Without that question, the algorithm is blind. It places a queen in a column that already has one, recurses deeper, eventually discovers the conflict at the bottom of the tree, and backtracks all the way up. It did all that work for nothing.

With that question, the algorithm checks before recursing. “Column 3 is taken — skip it.” The entire subtree under that choice is never explored. One check eliminates thousands of dead-end paths.

This is not an optimization you add later. Pruning is the algorithm. Without it, backtracking is just brute-force depth-first search with extra steps. The constraint check before the choose step is what gives backtracking its power.

There are two places you could put the constraint check. Both produce correct results. But one is dramatically more efficient.

Option A: Check before choosing. In the for-loop, before pushing a candidate onto the path, check if it would exceed the target. If so, continue — skip this candidate entirely.

Option B: Check inside the recursive call. Push every candidate onto the path, recurse, and let the next call discover that remaining is negative. Then backtrack.

Both find the same solutions. But Option B enters dead-end subtrees and only discovers the dead end one level deeper. Option A never enters them at all.

See for yourself — run both and count the nodes.

for (const c of candidates) {
  if (remaining - c < 0) continue; // PRUNE first
  path.push(c);
  backtrack(remaining - c);
  path.pop();
}

for (const c of candidates) {
  path.push(c);
  backtrack(remaining - c);
  path.pop();
  // prune check happens inside recursive call
}

You played gatekeeper, counted the nodes, and saw where pruning belongs. Now write the function.

Combination Sum: given candidates that can be reused, find all combinations summing to a target. Fill in the four blanks: when to stop, when to prune, how to recurse (watch the start index), and how to undo.

Three questions on pruning — why it matters, where to put it, and how it affects complexity.