combination-sum.ts

/**
 * 39. Combination Sum  (Medium)
 * Link: https://leetcode.com/problems/combination-sum/
 *
 * Given an array of distinct `candidates` and a `target`, return all unique
 * combinations that sum to target. The same number may be chosen an unlimited
 * number of times. Combinations differing only in order count as the same.
 *
 * Example:
 *   Input:  candidates = [2, 3, 6, 7], target = 7
 *   Output: [[2, 2, 3], [7]]
 *
 * Approach:
 *   Backtracking with a `start` index to enforce non-decreasing choices (avoids
 *   permutations of the same combination). Because reuse is allowed we recurse
 *   with the same index `i`, subtracting the candidate from the remaining
 *   target. Prune when the remaining target goes negative.
 *
 * Time:  O(n^(target/min))  — exponential in the worst case.
 * Space: O(target/min)      — recursion depth / current path.
 */
export function combinationSum(
  candidates: number[],
  target: number,
): number[][] {
  const result: number[][] = [];
  const path: number[] = [];

  function backtrack(start: number, remaining: number): void {
    if (remaining === 0) {
      result.push([...path]);
      return;
    }
    for (let i = start; i < candidates.length; i++) {
      if (candidates[i] > remaining) continue; // prune (works best if sorted)
      path.push(candidates[i]);
      backtrack(i, remaining - candidates[i]); // reuse allowed -> pass i
      path.pop();
    }
  }

  backtrack(0, target);
  return result;
}