Lesson 13.3 · Backtracking
Pruning and Avoiding Duplicates
Stop branches that can't succeed, and when the input has duplicates, sort it and skip equal values at the same depth.
14 min
Think of it like this
Planning routes for a road trip with a fuel budget: as soon as a route has used too much fuel, you stop extending it. And if two towns on the list are identical, picking the first or the second gives the same trip, so you only consider the first.
1.Pruning
Check constraints before recursing: a running sum already above the target, too many open brackets, a queen attacked by another. With sorted input, you can often break instead of continue, because every later option is even worse.
2.Skipping duplicates
With input [1, 2, 2], choosing the first 2 or the second 2 at the same depth produces identical subtrees. Sort the input, then inside the loop skip i > start && nums[i] == nums[i − 1]. The i > start part still allows the second 2 deeper in the same branch, so [2, 2] is generated once.
sorted nums = [1, 2, 2]path(list)
Step 1/3Under [1], choosing index 1 (2) gives [1,2], and deeper [1,2,2].
Remember
- Prune as early as possible; with sorted input, break.
- Sort + skip
i > start && a[i] == a[i−1]removes duplicate answers. - For permutations with duplicates, skip when the previous equal element isn't used.
Common mistakes
- Removing duplicates with a Set of results afterwards (works but wastes exponential work).
- Skipping with
i > 0instead ofi > start(loses answers like [2,2]).