DSAPrep
MediumBacktracking

Combination Sum II

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
View original on LeetCode ↗

This is Combination Sum with two twists: each element can be used at most once, and the input array itself may contain duplicate values that must not produce duplicate combinations.

Brute Force: Index-Based Backtracking + Set Dedup

Time O(2^n · n log n)Space O(2^n · n)

Reuse the plain “include or exclude index i” recursion from Subsets/Combination Sum (advancing to i + 1 so nothing repeats), collect every combination that sums to target, then dedupe by sorting each combination and dropping repeats via a set.

class Solution:
    def combinationSum2(self, candidates: list[int], target: int) -> list[list[int]]:
        n = len(candidates)
        seen = set()
        result = []


        def backtrack(start, path, remaining):
            if remaining == 0:
                key = tuple(sorted(path))
                if key not in seen:
                    seen.add(key)
                    result.append(list(key))
                return
            if remaining < 0 or start == n:
                return
            path.append(candidates[start])
            backtrack(start + 1, path, remaining - candidates[start])
            path.pop()
            backtrack(start + 1, path, remaining)


        backtrack(0, [], target)
        return result

Correct, but wasteful: it explores every one of the 2^n include/exclude subsets (many redundant, since duplicate values create identical subtrees) and pays extra to sort and hash each result just to filter duplicates after the fact.

Sort + Skip Adjacent Duplicates at Each Depth

OptimalTime O(2^n)Space O(n)

Sort candidates first so equal values sit next to each other. In the loop over choices at a given recursion depth, if the current candidate equals the previous one at the same depth (i > start), skip it — that value has already been fully explored as “the first duplicate used here,” so trying it again only reproduces combinations already found. This prunes duplicates at the source instead of filtering afterward, and a candidate is never revisited within the same combination since the recursive call moves to i + 1.

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


        def backtrack(start, remaining):
            if remaining == 0:
                result.append(path[:])
                return
            for i in range(start, len(candidates)):
                if i > start and candidates[i] == candidates[i - 1]:
                    continue  # skip duplicate values at this depth
                if candidates[i] > remaining:
                    break  # sorted, so nothing further fits either
                path.append(candidates[i])
                backtrack(i + 1, remaining - candidates[i])
                path.pop()


        backtrack(0, target)
        return result

Why it is correct: within one call to backtrack, the i > start check only fires on the second and later occurrences of a value at that position, so the first occurrence is always tried — nothing is missed, only re-tries of an identical value at an identical decision point are cut. Complexity: the duplicate-skip prunes many branches, but worst case (all distinct values) still explores the 2^n include/exclude subsets → O(2^n) time; recursion depth and path are bounded by n → O(n) auxiliary space, with no post-hoc dedup structure needed.