Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumbacktracking

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

Reuse-allowed DFS

Tested only

Time O(n^(T/min))Space O(T/min)

Idea. dfs(start, remain): if 0 record; for i>=start if candidates[i] is at most remain take and dfs(i).

Walkthrough. candidates=[2,3,6,7], target=7 → [2,2,3] and [7].

Trade-offs. Unlike permutations, start index avoids order duplicates.

Solution

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

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?