39. Combination Sum

Given distinct integers candidates and a target, return all unique combinations of candidates that sum to target. The same number may be chosen any number of times.

Build combinations in non-decreasing index order so each set is generated once. Reuse the same index to allow repeats, and stop early once a candidate overshoots (they are sorted).

1function combinationSum(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 (candidates[i] > remain) break;
8      path.push(candidates[i]);
9      dfs(i, remain - candidates[i]);
10      path.pop();
11    }
12  }
13  dfs(0, target);
14  return res;
15}

path = []

candidates

results

empty

Sort the candidates so we can prune.

1 / 0

Space: play/pause · ←/→: step