Combination Sum II

Difficulty: Medium Source: NeetCode

Problem

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination. The solution set must not contain duplicate combinations.

Example 1: Input: candidates = [10, 1, 2, 7, 6, 1, 5], target = 8 Output: [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]

Example 2: Input: candidates = [2, 5, 2, 1, 2], target = 5 Output: [[1, 2, 2], [5]]

Constraints:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

Prerequisites

Before attempting this problem, you should be comfortable with:

• Combination Sum I — the version where reuse is allowed and all candidates are distinct
• Backtracking — exploring and pruning a decision tree
• Duplicate handling — sorting to group duplicates and skipping at the same recursion level

1. Brute Force

Intuition

Sort the candidates. Generate every possible subset of candidates (each element used at most once). For each subset that sums to target, convert it to a sorted tuple and add to a set to avoid duplicate results. Return the deduplicated list. This is wasteful because we build many subsets that can never sum to target, but it’s conceptually simple.

Algorithm

1. Sort candidates.
2. Use backtracking to enumerate all subsets.
3. If a subset sums to target, add its tuple to a result set.
4. Convert the set back to a list of lists.

Solution

def combinationSum2_brute(candidates, target):
    candidates.sort()
    result_set = set()

    def backtrack(start, current, remaining):
        if remaining == 0:
            result_set.add(tuple(current))
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break
            current.append(candidates[i])
            backtrack(i + 1, current, remaining - candidates[i])
            current.pop()

    backtrack(0, [], target)
    return [list(t) for t in result_set]


print(sorted(combinationSum2_brute([10, 1, 2, 7, 6, 1, 5], 8)))
# [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
print(sorted(combinationSum2_brute([2, 5, 2, 1, 2], 5)))
# [[1, 2, 2], [5]]

Complexity

• Time: O(2^n * n) — exponential subsets, each costs O(n) to hash
• Space: O(n) — recursion depth

2. Backtracking with Duplicate Skipping

Intuition

Sort candidates first so duplicates are adjacent. During backtracking, after picking candidates[i] and recursing, if the next element candidates[i+1] has the same value as candidates[i], skip it entirely. This prevents starting the same subtree twice from the same position in the recursion, which is exactly what causes duplicate results. Each element is still used at most once (we pass i + 1 when recursing).

Algorithm

1. Sort candidates.
2. Define backtrack(start, current, remaining).
3. If remaining == 0: record current and return.
4. For i from start to end:
   • Skip if i > start and candidates[i] == candidates[i - 1] (same value at same level).
   • Skip if candidates[i] > remaining (prune — sorted order makes this a break, not continue).
   • Append candidates[i], recurse with i + 1, pop.

Solution

def combinationSum2(candidates, target):
    candidates.sort()
    result = []

    def backtrack(start, current, remaining):
        if remaining == 0:
            result.append(list(current))
            return
        for i in range(start, len(candidates)):
            # skip duplicates at the same recursion level
            if i > start and candidates[i] == candidates[i - 1]:
                continue
            # prune: sorted array, so all remaining are too large
            if candidates[i] > remaining:
                break
            current.append(candidates[i])
            backtrack(i + 1, current, remaining - candidates[i])
            current.pop()

    backtrack(0, [], target)
    return result


print(combinationSum2([10, 1, 2, 7, 6, 1, 5], 8))
# [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
print(combinationSum2([2, 5, 2, 1, 2], 5))
# [[1, 2, 2], [5]]
print(combinationSum2([1, 1, 1, 1], 2))
# [[1, 1]]

Complexity

• Time: O(2^n) — in the worst case (all distinct), explores every subset
• Space: O(n) — recursion depth

Common Pitfalls

Using i > 0 instead of i > start for the duplicate check. The condition i > start and candidates[i] == candidates[i-1] means “skip if we’re not the first element at this recursion level and the previous element had the same value.” Using i > 0 instead is wrong — it would skip valid combinations like [1, 1, 6] where you legitimately pick the second 1 at a deeper level.

Passing i instead of i + 1 when recursing. Unlike Combination Sum I, each number can only be used once. Pass i + 1 to move past the current element.

Forgetting to sort. Without sorting, duplicates aren’t adjacent and the skip condition candidates[i] == candidates[i-1] doesn’t catch all duplicates. Always sort first.