#40
Combination Sum II
Medium Backtracking, use once, skip duplicates
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Each candidate may be used at most once and the list may contain duplicates. Return all unique combinations that sum to target.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: combinations to target, each number used once, input has repeats.
Why this works: recurse with i + 1 and skip equal values at the same level.
Example: [10, 1, 2, 7, 6, 1, 5], target 8 → sorted [1, 1, 2, 5, 6, 7, 10]
[1,1,6] [1,2,5] [1,7] [2,6]✦Hints open one at a time
Recurse with i + 1 because each number is used once.
Sort, and skip equal values at the same level (i > start).
↗Approach
Same template as Subsets II with a target: sort, skip duplicates at each level, break when the candidate exceeds the remaining sum.
</>Solution (Java)
import java.util.*;
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> res = new ArrayList<>();
backtrack(candidates, 0, target, new ArrayList<>(), res);
return res;
}
private void backtrack(int[] c, int start, int remaining, List<Integer> path, List<List<Integer>> res) {
if (remaining == 0) {
res.add(new ArrayList<>(path));
return;
}
for (int i = start; i < c.length && c[i] <= remaining; i++) {
if (i > start && c[i] == c[i - 1]) continue; // skip duplicate at this level
path.add(c[i]);
backtrack(c, i + 1, remaining - c[i], path, res);
path.remove(path.size() - 1);
}
}
}!Common mistake
Using a HashSet of lists to de-duplicate — slow, and it hides the clean skip rule.
Complexity
- Time: O(2^n) worst case.
- Space: O(n).
Topic: Recursion & Backtracking
🎬 Episodes 29–36: video coming soon