Medium
ArrayBacktracking
Updated Sep 2026

Combination Sum II

Asked at Amazon

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.

Asked At

CompanyDifficulty
AmazonMediumView all Amazon questions →

How to Think About It

1.

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.

2.

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.

3.

Visual walkthrough for candidates = [1, 1, 2, 5, 6, 7], target = 8:
Sort: [1, 1, 2, 5, 6, 7]

  • Include first 1 (index 0): remaining target=7. Try including 1 (index 1): remaining=6. Try 2: remaining=4. Try 5: remaining=-1. Backtrack.
  • Skip second 1 (index 1, same as index 0): avoid duplicate [1,1,...].
  • Include 2 (index 2): remaining=6. Try 5: remaining=1. No match. Try 6: remaining=0. Found [2,6].
  • Continue systematically.
    Result: [[1,1,6], [1,2,5], [1,7], [2,6]].
4.

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.

5.

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.

6.

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, 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: 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.
  • 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.

What Trips People Up in Real Interviews

1.

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.

2.

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].

3.

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.

4.

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.

5.

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

def 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 result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.

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.