40. Combination Sum II
Asked at Amazon
Difficulty
Medium
Time
O(2^n)
Space
O(n)
Pattern
Array
Companies
1
Problem
You are given a list of numbers called candidates and a target number. Find every combination of numbers from candidates whose sum equals target.
Two rules change the answer. First, each position in candidates may be used at most once in a combination. Second, candidates can contain repeated values, but the final list must not contain the same combination twice — for example [1,2,5] and [1,2,5] picked from different positions count as one answer.
Return the list of combinations in any order. Each combination is a list of numbers.
Pick numbers, each position once
Constraints
- ●
1 <= candidates.length <= 100 - ●
1 <= candidates[i] <= 50 - ●
1 <= target <= 30
Examples
candidates = [10,1,2,7,6,1,5], target = 8[[1,1,6],[1,2,5],[1,7],[2,6]]candidates = [2,5,2,1,2], target = 5[[1,2,2],[5]]Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Amazon | Medium | View all Amazon questions → |
How to Think About It
Backtracking with sorting: sort the candidates first. This lets you skip duplicates and prune branches early. At each step, choose whether to include or exclude the current number.
Key difference from Combination Sum I: each number can only be used once (no repetition), and candidates may contain duplicates. You must skip over duplicate values to avoid duplicate combinations.
The dedup rule: after sorting, if candidates[i] == candidates[i-1] and i > startIndex, skip candidates[i]. This prevents picking the same value at the same recursion depth, which would create duplicate combinations.
Pruning: if the current candidate exceeds the remaining target, you can skip all subsequent candidates (since the array is sorted). This is a significant optimization.
Edge cases: candidates has all duplicates (e.g., [1,1,1,1] target=4), target is 0 (return [[]] if we consider empty set, but the problem says target > 0), no valid combinations (return []).
Optimal Approach
Step 1: Sort the candidates array.
Step 2: Define a backtracking function with parameters: current index, remaining target, current combination, result list.
Step 3: Base case: if remaining target == 0, add current combination to result.
Step 4: For each index i from start to end:
- If i > start and candidates[i] == candidates[i-1], skip (dedup)
- If candidates[i] > remaining target, break (pruning, since sorted)
- Include candidates[i], recurse with i+1 and remaining - candidates[i]
- Backtrack (remove last element)
Step 5: Return result.
Walkthrough for candidates = [1, 1, 2, 5, 6, 7], target = 8:
- Sort: [1, 1, 2, 5, 6, 7]
- Backtrack(0, 8, [], [])
- i=0: include 1. Backtrack(1, 7, [1], [])
- i=1: include 1. Backtrack(2, 6, [1,1], [])
- i=2: include 2. Backtrack(3, 4, [1,1,2], [])
- i=3: 5 > 4, break.
- i=3: include 5. Backtrack(4, -1, ...). -1 < 0, return.
- i=4: include 6. Backtrack(5, 0, [1,1,6], []). 0 == 0, add [1,1,6].
- i=5: 7 > 0, break.
- i=2: include 2. Backtrack(3, 4, [1,1,2], [])
- i=2: include 2. Backtrack(3, 5, [1,2], [])
- i=3: include 5. Backtrack(4, 0, [1,2,5], []). 0 == 0, add [1,2,5].
- i=5: include 7. Backtrack(6, 0, [1,7], []). 0 == 0, add [1,7].
- i=1: include 1. Backtrack(2, 6, [1,1], [])
- i=1: skip (candidates[1] == candidates[0] and i > start)
- i=2: include 2. Backtrack(3, 6, [2], [])
- i=4: include 6. Backtrack(5, 0, [2,6], []). 0 == 0, add [2,6].
- i=3: 5 > 8? No. include 5. Backtrack(4, 3, [5], [])
- i=4: 6 > 3, break.
- i=4: 6 < 8. include 6. Backtrack(5, 2, [6], [])
- i=5: 7 > 2, break.
- i=5: 7 < 8. include 7. Backtrack(6, 1, [7], [])
- No more elements.
- i=0: include 1. Backtrack(1, 7, [1], [])
- Result: [[1,1,6], [1,2,5], [1,7], [2,6]]
Time: O(2^n) in the worst case. Space: O(n) for recursion depth.
Sort, then backtrack with dedup
What Trips People Up in Real Interviews
Forgetting to sort first. Without sorting, you can't detect or skip duplicates. Sorting is a prerequisite for the dedup logic to work. Always sort before backtracking with duplicates.
Using a HashSet to deduplicate combinations instead of skipping during backtracking. A HashSet wastes space and time. The correct approach is to skip duplicates at the source by checking candidates[i] == candidates[i-1].
Not distinguishing between same-value elements at different recursion depths. If candidates = [1, 1, 2], the first 1 at depth 0 and the second 1 at depth 1 can both be in the same combination [1, 1, 2]. The dedup rule only applies at the same depth.
Including the current element AND excluding it in the same recursive call. The backtracking pattern is: include current, recurse, backtrack, then exclude current and move to the next. Don't do both simultaneously.
Forgetting to pass the start index. Each recursive call should start from the next index (i + 1), not from 0. Starting from 0 creates permutations, not combinations, and leads to duplicate results.
Solution Code
O(2^n) timedef combinationSum2(candidates, target):
candidates.sort()
result = []
def backtrack(start, remaining, path):
if remaining == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
if i > start and candidates[i] == candidates[i - 1]:
continue
if candidates[i] > remaining:
break
path.append(candidates[i])
backtrack(i + 1, remaining - candidates[i], path)
path.pop()
backtrack(0, target, [])
return resultFrequently Asked Questions
What is the Combination Sum II problem?
Given a collection of candidate numbers (with duplicates) and a target number, find all unique combinations where the candidate numbers sum to target. Each number in the candidates may only be used once, and the solution set must not contain duplicate combinations.
How do you solve Combination Sum II?
The optimal approach runs in O(2^n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Combination Sum II?
Combination Sum II is asked at Amazon. It is a medium difficulty problem.
What are common mistakes on Combination Sum II?
- Forgetting to sort first. Without sorting, you can't detect or skip duplicates. Sorting is a prerequisite for the dedup logic to work. Always sort before backtracking with duplicates.
- Using a `HashSet` to deduplicate combinations instead of skipping during backtracking. A `HashSet` wastes space and time. The correct approach is to skip duplicates at the source by checking `candidates[i] == candidates[i-1]`.
- Not distinguishing between same-value elements at different recursion depths. If candidates = [1, 1, 2], the first 1 at depth 0 and the second 1 at depth 1 can both be in the same combination [1, 1, 2]. The dedup rule only applies at the same depth.
- Including the current element AND excluding it in the same recursive call. The backtracking pattern is: include current, recurse, backtrack, then exclude current and move to the next. Don't do both simultaneously.
- Forgetting to pass the start index. Each recursive call should start from the next index (i + 1), not from 0. Starting from 0 creates permutations, not combinations, and leads to duplicate results.