Combination Sum II
Problem Statement
Given an array candidates that may contain duplicate positive integers and an integer target, return all unique combinations whose selected numbers sum to target. Each candidate occurrence may be used at most once. The answer must not contain duplicate combinations.
Input
An integer array candidates, possibly with duplicate values, and an integer target.
Output
A list of unique combinations where each array position is used at most once and each combination sums to target.
Constraints
- •
1 <= candidates.length <= 100 - •
1 <= candidates[i] <= 50 - •
1 <= target <= 30
Examples
Example 1
candidates = [10,1,2,7,6,1,5], target = 8
[[1,1,6],[1,2,5],[1,7],[2,6]]Example 2
candidates = [2,5,2,1,2], target = 5
[[1,2,2],[5]]Example 3
candidates = [1,1,1], target = 2
[[1,1]]Learning Objectives
- Apply start-index recursion when each occurrence can be used at most once.
- Sort the input so equal values become adjacent and can be skipped at the same depth.
- Use **i > start && candidates[i] == candidates[i - 1]** to avoid duplicate combinations.
- Prune target-sum branches with a sorted early break.
Intuition
Pattern Recognition
This is a combination sum with two added constraints: each array occurrence is one-use, and equal values can create duplicate result rows. The no-reuse part is solved by recursing with i + 1 after choosing index i. The duplicate part is solved by sorting and skipping equal values that would start the same choice at the same recursion depth.
The skip rule is depth-sensitive. If i > start and candidates[i] == candidates[i - 1], choosing this value would create the same subtree already created by the previous equal value at this depth. But when the previous equal value is already in the path from an earlier depth, the current equal value may still be chosen, which is how [1,1,6] remains valid.
Common mistakes
- ×Skipping every duplicate value globally, which incorrectly prevents combinations such as **[1,1,6]**.
- ×Using **i** instead of **i + 1** in the recursive call, which allows the same occurrence to be reused.
- ×Applying the duplicate-skip rule before sorting the array.
- ×Continuing after **candidate > remaining** even though the sorted suffix cannot help.
Algorithm Explanation
State
Each frame stores start, the first unused occurrence index available to this path, remaining, and path. Because each chosen occurrence advances to i + 1, no occurrence can be reused.
Recursion tree
For candidates = [10,1,2,7,6,1,5], sorting gives [1,1,2,5,6,7,10]. At the root, the first 1 opens all combinations beginning with 1, including the child that chooses the second 1 and later 6 to form [1,1,6]. When the root loop reaches the second 1, it is skipped because it would create another root subtree beginning with 1. Later, branches [1,2,5], [1,7], and [2,6] reach target 8. Values greater than the remaining sum stop their loops.
Pruning
Sort first. If i > start and the current value equals the previous value, skip it to avoid duplicate sibling branches. If candidates[i] > remaining, break because every later value is at least as large. If remaining == 0, add a copy of the path.
Algorithm
- Sort candidates.
- Start DFS with start = 0, remaining = target, and an empty path.
- If remaining == 0, add a copy of path.
- For each i from start onward, skip candidates[i] when it equals the previous value at the same depth.
- Break if candidates[i] > remaining.
- Choose candidates[i], recurse with start = i + 1, then unchoose it.
Solutions
Solution: Sorted one-use DFS with sibling duplicate skip
Sorting groups equal values together. The helper advances to i + 1 so each occurrence is used at most once, and the sibling skip removes duplicate subtrees without blocking valid repeated values across different depths.
Step-by-step
- Sort the candidate array so duplicates are adjacent.
- Start DFS with the full target as the remaining sum.
- At each depth, iterate from start to the end of the array.
- Skip a value if it equals the previous value and the previous value was a sibling choice at this same depth.
- Stop the loop once the value exceeds the remaining sum.
- Choose the value, recurse from index + 1, and then remove it.
O(2^n * n)
O(n)
In the worst case the DFS explores subsets of the n occurrences and copies length-n paths into the output. Sorting costs O(n log n).
Java implementation
Dry Run
Sample input
candidates = [10,1,2,7,6,1,5], target = 8. After sorting, use [1,1,2,5,6,7,10].
| depth | start | choice | path and sum | action |
|---|---|---|---|---|
| 0 | 0 | 1 at index 0 | [1], remaining 7 | choose first 1 |
| 1 | 1 | 1 at index 1 | [1,1], remaining 6 | allowed because it is deeper, not a skipped sibling |
| 2 | 2 | 6 at index 4 | [1,1,6], remaining 0 | add combination |
| 1 | 1 | 2 at index 2 | [1,2], remaining 5 | choose 2 after first 1 |
| 2 | 3 | 5 at index 3 | [1,2,5], remaining 0 | add combination |
| 1 | 1 | 7 at index 5 | [1,7], remaining 0 | add combination |
| 0 | 0 | 1 at index 1 | [] remaining 8 | skip duplicate sibling because previous value was also 1 |
| 0 | 0 | 2 at index 2 | [2], remaining 6 | choose 2 from root |
| 1 | 3 | 6 at index 4 | [2,6], remaining 0 | add combination |
| 0 | 0 | 10 at index 6 | [] remaining 8 | break because 10 exceeds remaining |
The second 1 is skipped only as a root sibling. It is still available after choosing the first 1, which preserves valid combinations with repeated equal values.
Interview Tips
The duplicate skip is the centerpiece. Explain it as skipping duplicate siblings, not duplicate values everywhere. Use the phrase i > start to show that the previous equal value must be at the same recursion depth. Then contrast with Combination Sum: this problem advances to i + 1 because each occurrence is one-use.
Likely follow-ups
- What breaks if the array is not sorted first?
- How would you modify the solution to return combinations in descending order?
- How would you count unique combinations without materialising them?
- How does the skip rule differ from the one used in duplicate permutations?
Similar Problems
Key Takeaways
- One-use candidates recurse with **i + 1**.
- Sort duplicates before trying to skip them.
- Skip equal sibling choices with **i > start** to avoid duplicate combinations.
- A sorted early break cuts every suffix once the candidate exceeds the remaining target.