MEDIUM

Combination Sum II

Given a collection of candidate numbers candidates (which may contain duplicates) and a target integer target, find all unique combinations where the numbers sum to target. Each number may be used at most once per combination.

Example

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

Output [[1,1,6],[1,2,5],[1,7],[2,6]]

Key Pointers

This combines two rules: numbers can't repeat (unlike plain Combination Sum), so the recursion advances to i + 1, not i.
Sorting first enables both the same-level duplicate skip and early-break pruning once a candidate exceeds the remaining target.
The duplicate-skip check (i > start and candidates[i] == candidates[i - 1]) prevents identical combinations from being built via different index paths — no need to dedupe the final result afterward.

Step-by-Step Analysis

Sort candidates.
Define backtrack(start, remaining): if remaining == 0, record a copy of path.
Loop i from start to len(candidates): break if candidates[i] > remaining (sorted, so nothing later fits either).
Skip i if i > start and candidates[i] == candidates[i - 1] (avoids duplicate combinations at this level).
Otherwise append candidates[i], recurse with backtrack(i + 1, remaining - candidates[i]), then pop.
Call backtrack(0, target) and return the result.

Complexity

Time: O(2ⁿ) worst case — Space: O(n) recursion depth

Code

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

    def backtrack(start: int, remaining: int) -> None:
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break
            if i > start and candidates[i] == candidates[i - 1]:
                continue
            path.append(candidates[i])
            backtrack(i + 1, remaining - candidates[i])
            path.pop()

    backtrack(0, target)
    return result

Code Explanation

How the solution above works, piece by piece.

Sort so duplicates are adjacent and the loop can break once a candidate exceeds remaining.
remaining == 0: record the combination.
if i > start and candidates[i] == candidates[i - 1]: continue: skip an equal value at the same level, which would only repeat a combination already explored.
Recurse with i + 1: each element is used at most once.
Pop to backtrack. The pruning keeps the real work far below the 2ⁿ worst case.

Visual Walkthrough

The recursion tree for candidates = [10, 1, 2, 7, 6, 1, 5], target = 8:

Sorted candidates are [1, 1, 2, 5, 6, 7, 10]. Each number is used at most once (i + 1), and at each level an equal neighbour is skipped so [1, 2, 5] isn't found twice. Blue leaves are the 4 answers: 1+1+6, 1+2+5, 1+7, 2+6.

remaining 0 → answerdead end

Video Explanation

NeetCode — Combination Sum II, Backtracking, LeetCode 40