medium

Combination Sum

Find every combination of numbers from a list that adds up to a target, reusing numbers freely.

1. Define the problem

Combination Sum

Given an array of distinct positive integers candidates and a target integer target, return all unique combinations of candidates where the chosen numbers sum to target. The same number may be chosen an unlimited number of times . Sort the candidates first, then use backtracking that tries a candidate, subtracts it from the remaining target, and recurses without moving the start index forward (so it can be reused) — but prunes the rest of the loop the moment a candidate alone would overshoot what's left.

Constraints

  • 2 ≤ candidates.length ≤ 40
  • 1 ≤ candidatesi ≤ 40
  • All elements of candidates are distinct
  • 1 ≤ target ≤ 40

Example

Inputcandidates = [2, 3, 6, 7], target = 7
Output[[2,2,3],[7]]

Explanation 2 + 2 + 3 = 7 reuses 2 twice, and 7 alone also sums to 7.

2. Visualize the solution

Try a sorted candidate, prune once it would overshoot the remaining target

Try a sorted candidate, prune once it would overshoot the remaining target
Statustry

Try 2 (remaining 7 → 5): path=[2].

What happens in this step

path = [2], remaining = 5
choice: sorted[0]=2, try continuing

backtrack(0, 7) tries sorted[0]=2 (2 <= 7), pushes it, and recurses as backtrack(0, 5) — the start index stays 0 so 2 can be reused.
Step 1 of 5

Steps to visualize

  1. Sort the candidates so every later one is at least as large as the current one.
  2. Try the candidate at the current index — it may be reused, so the next call starts at the same index.
  3. The instant a candidate is larger than what's left, stop the loop at this level entirely — every later candidate is even bigger.
  4. When the remaining target reaches exactly 0, record the path as one combination.
  5. Undo the last candidate to try the next one at this level.
3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Try a sorted candidate, prune once it would overshoot the remaining target
Statustry

Try 2 (remaining 7 → 5): path=[2].

What happens in this step

path = [2], remaining = 5
choice: sorted[0]=2, try continuing

backtrack(0, 7) tries sorted[0]=2 (2 <= 7), pushes it, and recurses as backtrack(0, 5) — the start index stays 0 so 2 can be reused.
Step 1 of 5
4. Solution

Solution

solution.tsTypeScript
function combinationSum(candidates, target) {
  const sorted = candidates.slice().sort((a, b) => a - b);
  const result = [];
  const path = [];

  function backtrack(start, remaining) {
    if (remaining === 0) {
      result.push(path.slice());
      return;
    }

    for (let i = start; i < sorted.length; i++) {
      if (sorted[i] > remaining) break; // sorted, so every later candidate is worse too

      path.push(sorted[i]);
      backtrack(i, remaining - sorted[i]); // same index — the candidate can be reused
      path.pop();
    }
  }

  backtrack(0, target);
  return result;
}
Time
O(2^target) worst case
Space
O(target)
5. Test cases

Test cases

InputExpectedCovers
candidates = [2, 3, 6, 7], target = 7[[2,2,3],[7]]example from the docstring
candidates = [2, 3, 5], target = 8[[2,2,2,2],[2,3,3],[3,5]]multiple reuse depths for the same candidate
candidates = [2], target = 1[]no combination can reach an odd target with only even candidates
candidates = [1], target = 1[[1]]smallest valid match, one candidate used once
candidates = [1], target = 2[[1,1]]a single candidate reused to reach the target
candidates = [2, 4, 6], target = 8[[2,2,2,2],[2,2,4],[2,6],[4,4]]several branches pruned once a candidate alone would overshoot
candidates = [3], target = 7[]target is not a multiple of the only candidate

Keep reading