Run it in your head. What does this return?

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

Combination Sum II

Medium

Each element once, duplicates skipped at each level

Problem

Given candidates (with duplicates) and a target, return all unique combinations summing to target; each number used at most once.

In simple words

Sort, use each number at most once, and skip equal siblings to avoid duplicate combinations.

The idea

Sort first, then at each level iterate the remaining candidates and skip any value equal to the previous one at that same level. Recursing on i+1 uses each element at most once; the skip stops duplicate values producing duplicate combinations.

The trick

Sort so equal values sit together and can be skipped in one check.
Skip when `i > start && nums[i] == nums[i-1]` — the level guard matters.
Break out once the value exceeds the remaining target.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

←→stepspaceplay

1/2

Optimal

timeO(2^n)spaceO(n)

1sort(c)2f(i, target, cur):3  if target==0: output; return4  for j from i to n-1:5    if j>i and c[j]==c[j-1]: continue   // skip dup6    if c[j]>target: break7    cur.push(c[j]); f(j+1, target-c[j], cur); cur.pop()

Input

array: [10, 1, 2, 7, 6, 1, 5]

Output

answer: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: candidates = [10, 1, 2, 7, 6, 1, 5], target = 8
Output:: [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
Explanation:: Each number used once; duplicates skipped.

Example 2

Input:: candidates = [2, 5, 2, 1, 2], target = 5
Output:: [[1, 2, 2], [5]]
Explanation:: [1,2,2] and [5] make 5.

Example 3

Input:: candidates = [1, 1], target = 3
Output:: []
Explanation:: Can't reach 3 → none.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.