Combination Sum II

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.

Note: 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

Solution

Approach: Backtracking with Duplicate Skipping

The key insight is to sort first, use each element at most once, and skip duplicates at the same recursion level.

Implementation

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        candidates.sort()

        def backtrack(start, path, remaining):
            if remaining == 0:
                result.append(path[:])
                return

            if remaining < 0:
                return

            for i in range(start, len(candidates)):
                # Skip duplicates at same level
                if i > start and candidates[i] == candidates[i-1]:
                    continue

                # Prune: no point continuing if candidate > remaining
                if candidates[i] > remaining:
                    break

                path.append(candidates[i])
                # Move to i+1 since each element can only be used once
                backtrack(i + 1, path, remaining - candidates[i])
                path.pop()

        backtrack(0, [], target)
        return result

Complexity Analysis

Time Complexity: O(2^n), where n is the length of candidates. In worst case, we explore all possible combinations.
Space Complexity: O(n) for recursion depth.

Key Insights

Use Once Only: Unlike Combination Sum I, we pass i+1 not i, so each element is used at most once.
Duplicate Handling: Sorting + skipping duplicates at same level prevents duplicate combinations like [1₁,2] and [1₂,2].
Early Pruning: After sorting, if current candidate > remaining, all subsequent candidates will also exceed it.
Two Key Differences from Combination Sum I:
- Pass i+1 instead of i (no reuse)
- Skip duplicates at same recursion level
Example: For [1,1,2] target 3, we get [1,2] once, not twice, because we skip the second 1 at root level.