Combination Sum II

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

Watch the two prune rules work on the first example: skipped duplicates at the same depth turn red, oversized candidates halt the whole branch, and each hit is recorded.