Combination sum (backtracking)

Medium TimeExponential in target/candidates SpaceO(target) stack

Given a list candidates of distinct positive numbers and a target, return every combination adding up to it exactly — overshooting is not a solution. A candidate may be used any number of times, and combinations differing only in order count as the same combination.

Examples

Example 1

Input
candidates = [2, 3, 6, 7]target = 7
Output
[[2,2,3],[7]]
2 + 2 + 3 = 7 and 7 alone; 3 + 2 + 2 is the same combination reordered.

Example 2

Input
candidates = [5]target = 3
Output
[]
5 already overshoots 3, and there is nothing smaller, so no combination exists.

The Code

function backtrack(start, remaining, path, candidates, result) {
  if (remaining === 0) {
    result.push(path.slice());
    return;
  }
  if (remaining < 0) return;
  for (let i = start; i < candidates.length; i++) {
    path.push(candidates[i]);
    backtrack(i, remaining - candidates[i], path, candidates, result);
    path.pop();
  }
}
function combinationSum(candidates, target) {
  const result = [];
  backtrack(0, target, [], candidates, result);
  return result;
}
combinationSum([2, 3, 6, 7], 7);
Done

The first 18 calls, of 64. This one does not fit on a page.

Step through combinationSum([2, 3, 6, 7], 7) call by call

More like this

All backtracking examples (10) →