40. Combination Sum II

Given candidates (which may contain duplicates) and a target, return all unique combinations whose numbers sum to target. Each number may be used at most once.

Sort, then at each depth loop over the remaining candidates. Skip a value equal to the previous sibling (it would start the same combinations again) and stop once a value exceeds what is left.

1function combinationSum2(candidates: number[], target: number): number[][] {
2  candidates.sort((a, b) => a - b);
3  const res: number[][] = [], path: number[] = [];
4  function dfs(start: number, remain: number) {
5    if (remain === 0) { res.push([...path]); return; }
6    for (let i = start; i < candidates.length; i++) {
7      if (i > start && candidates[i] === candidates[i - 1]) continue;
8      if (candidates[i] > remain) break;
9      path.push(candidates[i]);
10      dfs(i + 1, remain - candidates[i]);
11      path.pop();
12    }
13  }
14  dfs(0, target);
15  return res;
16}

remain = 7path = [1]

candidates

start,i

result

empty

Take 1; 7 left.

1 / 0

Space: play/pause · ←/→: step