Combination Sum

MediumBacktrackingArrayBacktracking

Problem

You are given a list of distinct positive integers and a target sum. Return every combination of numbers from the list that adds up exactly to the target. Each number may be reused any number of times, and the same multiset of numbers in a different order should not appear twice in the output.

Example. For candidates [2, 3, 6, 7] and target 7, the valid combinations are [2, 2, 3] and [7].

Key idea

Because numbers can repeat, this is not a subset enumeration. From the target you repeatedly pick a candidate and reduce the target by its value until reaching zero exactly or overshooting. Trying every sequence naively wastes time on branches that can never reach the target, so the goal is to prune early and avoid emitting the same combination in two orders.

Fixing the order of consideration solves both problems at once. Walk the candidates by index: at each step, either use the candidate at the current index (staying there, since it may repeat) and recurse on the reduced target, or move to the next index. Never letting recursion look backward guarantees numbers appear in nondecreasing order within a combination, ruling out reordered duplicates for free. Record a combination once the running total hits the target exactly; with candidates sorted, a candidate larger than what remains means every later one is too large as well, so the branch can stop immediately.

Solution

function combinationSum(candidates: number[], target: number): number[][] {
  const sorted = [...candidates].sort((a, b) => a - b);
  const result: number[][] = [];
  const partial: number[] = [];

  function backtrack(index: number, remaining: number): void {
    if (remaining === 0) {
      result.push([...partial]);
      return;
    }
    if (index === sorted.length || sorted[index] > remaining) {
      // Sorted candidates only grow from here, so nothing further can fit either.
      return;
    }

    // Use the candidate at the current index, staying here since it may repeat.
    partial.push(sorted[index]);
    backtrack(index, remaining - sorted[index]);
    partial.pop();

    // Move on without using this candidate.
    backtrack(index + 1, remaining);
  }

  backtrack(0, target);
  return result;
}

Complexity

  • Time: exponential in the target and candidate count, bounded by the number of valid combinations found times their length, since pruning skips overshooting paths.
  • Space: O(target / smallest candidate). Recursion depth.

Watch out for

  • Sort the candidates first so the "stop once too large" pruning is valid.
  • Allow reuse of the current index when recursing, not just the next one; advancing unconditionally silently turns this into Combination Sum II.

Pattern

This is bounded-reuse backtracking: repeatedly choosing from a fixed set while shrinking a numeric target, pruned by sorted order. Combination Sum II and Coin Change reuse the same target-reduction idea with different reuse and duplicate rules.

Related questions