#39 - Combination Sum

MediumBacktracking

Given an array of distinct integers candidates and a target, return all unique combinations where the chosen numbers sum to target. The same number may be chosen an unlimited number of times. Combinations are returned in any order.

Input	Output
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]]

Solution Space

Try it

/**
 * Finds all unique combinations of candidates that sum to target.
 * Each candidate may be reused unlimited times.
 *
 * @param candidates Array of distinct positive integers
 * @param target     Target sum
 * @returns          All valid combinations
 */
export function combinationSum(
  candidates: number[],
  target: number,
): number[][] {
  const result: number[][] = [];
  candidates.sort((a, b) => a - b);

  function backtrack(start: number, remaining: number, path: number[]): void {
    if (remaining === 0) {
      result.push([...path]);
      return;
    }

    for (let i = start; i < candidates.length; i++) {
      if (candidates[i] > remaining) break; // pruning (sorted)
      path.push(candidates[i]);
      backtrack(i, remaining - candidates[i], path); // i, not i+1: allow reuse
      path.pop();
    }
  }

  backtrack(0, target, []);
  return result;
}

Approach: backtracking with pruning – sort candidates first, then recurse from the current index (allowing reuse). Break early when the candidate exceeds the remaining sum.

Time: O(n^(T/M)) – where T is the target and M is the smallest candidate (max recursion depth).

Space: O(T/M) – recursion depth.

#17 Letter Combinations of a Phone Number

#216 Combination Sum III