The problem. Given a collection of numbers candidates (which may contain duplicates) and a target, find all unique combinations that add up to target. Each number may be used only once, and the answer must not contain duplicate combinations.
candidates = [10, 1, 2, 7, 6, 1, 5], target = 8 -> [[1,1,6], [1,2,5], [1,7], [2,6]]
candidates = [2, 5, 2, 1, 2], target = 5 -> [[1,2,2], [5]]Two changes to Combination Sum. Each number is used once, so recurse with i + 1. And the input has duplicates, so — exactly as in Subsets II — sort it and, at each level, skip a value equal to the one just tried: if (i > start && nums[i] === nums[i − 1]) continue. The sorted order also gives the pruning break when a number is bigger than what's left.
function combinationSum2(candidates, target) { const nums = [...candidates].sort((a, b) => a - b); const seen = new Set(); const result = []; for (let mask = 0; mask < 1 << nums.length; mask++) { const pick = nums.filter((_, j) => mask & (1 << j)); const key = pick.join(","); if (pick.reduce((s, x) => s + x, 0) === target && !seen.has(key)) { seen.add(key); result.push(pick); } } return result;}Time O(n · 2ⁿ). Fine for 15 numbers; hopeless for 100.
Each node shows what's still needed; equal values at the same level are skipped, and big ones end the loop.
function combinationSum2(candidates, target) { const nums = [...candidates].sort((a, b) => a - b); const result = []; const path = []; const build = (start, left) => { if (left === 0) { result.push([...path]); return; } for (let i = start; i < nums.length; i++) { if (i > start && nums[i] === nums[i - 1]) continue; // same value at the same level: a repeat if (nums[i] > left) break; // too big, and so is everything after it path.push(nums[i]); build(i + 1, left - nums[i]); // i + 1: each number once path.pop(); } }; build(0, target); return result;}Time O(n · 2ⁿ) in the worst case, space O(n). In practice the sorted break and the duplicate skip cut the tree to a small fraction.
[1, 1, 1, 1], target 2: just [[1, 1]].[].i > start; the break only applies after sorting.