Combination Sum

Problem (restated)

Distinct candidates; unlimited reuse. Find all unique combinations that sum to target.

Intuition

DFS with start index (order fixed → uniqueness). Reuse by calling dfs(i) after pick, not i+1.

Approaches

export function combinationSum(candidates: number[], target: number): number[][] {
  const res: number[][] = [];
  const path: number[] = [];
  const dfs = (start: number, remain: number) => {
    if (remain === 0) { res.push([...path]); return; }
    for (let i = start; i < candidates.length; i++) {
      const x = candidates[i]!;
      if (x > remain) continue;
      path.push(x);
      dfs(i, remain - x);
      path.pop();
    }
  };
  dfs(0, target);
  return res;
}

export function combinationSum(candidates: number[], target: number): number[][] {
  const res: number[][] = [];
  const path: number[] = [];
  const dfs = (start: number, remain: number) => {
    if (remain === 0) { res.push([...path]); return; }
    for (let i = start; i < candidates.length; i++) {
      const x = candidates[i]!;
      if (x > remain) continue;
      path.push(x);
      dfs(i, remain - x);
      path.pop();
    }
  };
  dfs(0, target);
  return res;
}

Template connection

Backtracking with reuse.

Reflection

• A number may be reused, but the loop starts at i, so the order stays fixed. That cuts off permutations of the same combination.
• When the remainder hits 0, append a copy. Pushing the live list lets the next step rewrite every answer you already stored.
• Going past the target prunes the branch. Target 0, and an empty candidate list. The candidates are positive.