Combination Sum II
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): []
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;}