Combination Sum

The problem. Given an array of distinct integers candidates and a target, return all unique combinations of candidates that add up to target. The same number may be used any number of times. Two combinations are the same if they use the same numbers the same number of times.

Example

candidates = [2, 3, 6, 7], target = 7  ->  [[2, 2, 3], [7]]
candidates = [2, 3, 5], target = 8     ->  [[2, 2, 2, 2], [2, 3, 3], [3, 5]]
candidates = [2], target = 1           ->  []

The idea: start index, but stay on the same number

Use the loop-from-start template with one change: after taking candidates[i], recurse with start = i (not i + 1) — the same number may be taken again. Never going back to an earlier index keeps each combination in one order, so [2, 2, 3] isn't also built as [2, 3, 2]. Track the remaining target: at 0 the path is an answer. Sort the candidates, and the moment one is bigger than what's left, break — every later candidate is bigger still.

1. Take it again, or move on

The take-or-skip template, where "take" stays on the same index.

1function combinationSum(candidates, target) {2  const result = [];3  const path = [];4  const decide = (i, left) => {5    if (left === 0) { result.push([...path]); return; }6    if (i === candidates.length || left < 0) return;7    path.push(candidates[i]);                // take candidates[i] (and maybe again)8    decide(i, left - candidates[i]);9    path.pop();10    decide(i + 1, left);                     // or move on to the next candidate11  };12  decide(0, target);13  return result;14}

Time O(2^(t/m)) roughly, where t is the target and m the smallest candidate (the deepest path takes the smallest number t/m times); space O(t/m) for the path.

2. Sorted loop with pruning

1function combinationSum(candidates, target) {2  const sorted = [...candidates].sort((a, b) => a - b);3  const result = [];4  const path = [];5  const build = (start, left) => {6    if (left === 0) {                          // exactly the target: one answer7      result.push([...path]);8      return;9    }10    for (let i = start; i < sorted.length; i++) {11      if (sorted[i] > left) break;             // too big, and so is everything after it12      path.push(sorted[i]);13      build(i, left - sorted[i]);              // i, not i + 1: it may be used again14      path.pop();15    }16  };17  build(0, target);18  return result;19}

Same worst case, much smaller tree in practice: no call is ever made with a negative remainder, and the break skips every larger candidate at once. Space O(t/m).

Comparing the approaches

Edge cases to test

Variations