Backtracking · 125Medium
Combination Sum II
Given a collection candidates that may contain duplicates and a target, find all unique combinations summing to target. Each candidate may be used AT MOST ONCE.
Constraints
- 1 <= candidates.length <= 100
- 1 <= candidates[i] <= 50
- 1 <= target <= 30
Examples
combinationSum2([10,1,2,7,6,1,5], 8) -> [[1,1,6], [1,2,5], [1,7], [2,6]] combinationSum2([2, 5, 2, 1, 2], 5) -> [[1,2,2], [5]] combinationSum2([1], 1) -> [[1]] // smallest input combinationSum2([2], 1) -> [] // no combination reaches the target combinationSum2([1, 1, 1], 2) -> [[1,1]] // one combination, not three combinationSum2([3, 1, 3, 5, 1, 1], 8) -> [[1,1,1,5], [1,1,3,3], [3,5]]
Edge cases
- Each element is usable once, but equal VALUES may legitimately appear twice (as [1,1,6]
- shows).
- No solution returns an empty array.
Show the target complexity (spoiler)
- Naive
- Enumerating all subsets and filtering by sum is O(2^n) with a costly de-duplication
- Target
- Backtracking on a sorted array: advance the index by one each level (single use) and skip a value equal to its predecessor within the same loop.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/10-backtracking/125-combination-sum-ii.js ./practice c 125