Combination Sum II

Medium

Problem

Return every unique combination of candidates that sums to target. Each candidate may be used at most once, and the candidates may contain duplicates, but the result 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]]

Test cases

Case 1

Input:    [10,1,2,7,6,1,5], 8
Expected (any order): [[1,1,6],[1,2,5],[1,7],[2,6]]

Case 2

Input:    [2,5,2,1,2], 5
Expected (any order): [[1,2,2],[5]]

Case 3

Input:    [1], 2
Expected (any order): []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Sort + skip duplicates + prune

Time O(2^n) worst caseSpace O(n)

Each number used at most once (recurse on i + 1). Skip equal siblings like Subsets II, and stop the loop once a candidate exceeds the remaining target.

function combinationSum2(cands, target) {
cands.sort((a, b) => a - b);
const res = [], path = [];
const bt = (start, rem) => {
if (rem === 0) { res.push([...path]); return; }
for (let i = start; i < cands.length && cands[i] <= rem; i++) {
if (i > start && cands[i] === cands[i - 1]) continue;
path.push(cands[i]);
bt(i + 1, rem - cands[i]);
path.pop();
}
};
bt(0, target);
return res;
}