Backtracking — Combination Sum II
↗ LeetCode: Combination Sum II · Medium · pattern chapter →
Combinations summing to target, each candidate used at most once; candidates may repeat.
Example 1 — candidates=[10,1,2,7,6,1,5], target=8 → [[1,1,6],[1,2,5],[1,7],[2,6]] (4 unique combos) Example 2 — candidates=[2,5,2,1,2], target=5 → [[1,2,2],[5]]Example 3 — candidates=[1,1,1], target=2 → [[1,1]]
Constraints — 1 ≤ n ≤ 100; 1 ≤ target ≤ 30.
Interview timer00:00
Approach 1 — Brute force (all subsets that sum + HashSet dedup)
Intuition. Enumerate every one of 2ⁿ subsets. For each, check if its elements sum to target. Put each valid subset (sorted) in a HashSet.
List<List<Integer>> combinationSum2Brute(int[] cand, int target) {
Arrays.sort(cand);
Set<List<Integer>> seen = new LinkedHashSet<>();
int n = cand.length;
for (int mask = 0; mask < (1 << n); mask++) {
int sum = 0;
List<Integer> combo = new ArrayList<>();
for (int i = 0; i < n; i++)
if ((mask & (1 << i)) != 0) { combo.add(cand[i]); sum += cand[i]; }
if (sum == target) seen.add(combo);
}
return new ArrayList<>(seen);
}Complexity — Time O(n · 2ⁿ); Space O(n · 2ⁿ). For n=100, 2¹⁰⁰ ≈ 10³⁰ — heat death of the universe. Even for n=25 it's 3·10⁷ — sluggish. In an interview state it as the reference, then upgrade.
Approach 2 — Sort + skip equal-at-same-depth + prune on sum (canonical)
Insight. Two prunes make this fast: (1) sort so we can break early when cand[i] > remaining; (2) skip duplicates at the same depth with i > start && a[i] == a[i-1]. Both cut the tree massively before recursion pays.
List<List<Integer>> combinationSum2(int[] cand, int target) {
Arrays.sort(cand);
List<List<Integer>> out = new ArrayList<>();
dfs(cand, 0, target, new ArrayList<>(), out);
return out;
}
void dfs(int[] a, int start, int rem, List<Integer> path, List<List<Integer>> out) {
if (rem == 0) { out.add(new ArrayList<>(path)); return; }
for (int i = start; i < a.length && a[i] <= rem; i++) {
if (i > start && a[i] == a[i-1]) continue;
path.add(a[i]);
dfs(a, i + 1, rem - a[i], path, out);
path.remove(path.size() - 1);
}
}Complexity — Time exponential worst case but heavily pruned; Space O(target). Say aloud in an interview: "the a[i] <= rem break is what makes this practical — without it, we'd recurse into every larger candidate for no reason."
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Brute + HashSet dedup | O(n · 2ⁿ) | O(n · 2ⁿ) | Reference; dies at n>25 |
| Sort + skip + prune | exponential (heavily pruned) | O(target) | Canonical |
When to use which
- Duplicates in candidates, each used once → sort + skip.
- Reuse allowed → Combination Sum.
- Fixed k, digits 1-9 → Combination Sum III.