Pruning, Duplicates and Grids

Backtracking, lesson 3 of 3

Pruning, Duplicates and Grids

Cut dead branches early, skip duplicate answers, and search grids safely.

14 min, 0 of 3 activities solved

Getting Python ready… examples can run in a moment.

Pruning means abandoning a branch the moment you can prove it can't lead to an answer. The answers don't change, but whole subtrees vanish.

Classic example: pick numbers (reuse allowed) that add up to a target. If the candidates are sorted and the current one already exceeds what's left, every later one does too, so you can break out of the loop, not just continue.

Example

Measure the effect of pruning

Same number of answers, far fewer calls. Pruning rules to look for: a running sum over the target, a partial string that's already invalid, a queen that's already attacked, a letter that doesn't match.

Duplicates in the input. Subsets of [1, 2, 2] would produce [1, 2] twice (once with each 2). The fix has two parts:

Sort so equal values sit next to each other.
At one level of the tree, skip a value equal to the previous sibling: if i > start and nums[i] == nums[i - 1]: continue

path [1], start = 1, choices: 2a 2b
  pick 2a → builds [1,2] and [1,2,2]
  pick 2b → would build [1,2] again: skip

It's i > start, not i > 0: going deeper with the second 2 (to make [1, 2, 2]) is fine, only picking it as a sibling repeats work.

Example

Subsets with duplicates

Six subsets, none repeated. Try deleting the skip line and count again.

Quiz

This version skips with i > 0 instead of i > start. How many subsets does it return?

Backtracking on a grid. Searching for a path in a grid (like spelling a word through neighbouring cells) is the same template. The "choice" is which neighbour to step to, and the state is which cells are already on the path.

Mark the cell as visited (overwrite it with "#", or add it to a set).
Explore the 4 neighbours.
Restore the cell before returning.

Why restore? A cell used by one path may be needed by a different path explored later. Marking without restoring turns "not on this path" into "never usable again".

Example

Count simple paths across a grid

These count paths from the top-left to the bottom-right corner that never revisit a cell (3×3 has 12). Comment out the restore line and the count collapses, because cells stay blocked after the first path uses them.

Quiz

In a grid word search, why do you put the letter back after exploring a cell?

Another path explored later may need to pass through that cell

To make the search run in linear time

Because Python lists can't be modified during recursion

So the final answer includes the letter

Exercise

Combination Sum II

Write combination_sum2(cands, target): return every unique combination of numbers from cands that adds up to target. Each position in cands may be used at most once, but cands can contain repeated values, and the answer must not contain the same combination twice. Any order.

combination_sum2([10, 1, 2, 7, 6, 1, 5], 8) → [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]

You'll need all three ideas: sort, skip equal siblings, and prune with break.