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 (yeniden ifade)

Ayrı adaylar; sınırsız yeniden kullanım. Toplamı target olan tüm benzersiz kombinasyonları bul.

Sezgi

Başlangıç indeksli DFS (sıra sabit → benzersizlik). Alındıktan sonra dfs(i) çağır, i+1 değil — yeniden kullanım böyle olur.

Yaklaşımlar

Yeniden kullanıma izin veren DFS

Doğrulanmadı

Zaman O(n^(T/min))Alan O(T/min)

Fikir. dfs(start, remain): 0 ise kaydet; i>=start için candidates[i] remain’den büyük değilse al ve dfs(i).

Yürüyüş. candidates=[2,3,6,7], target=7 → [2,2,3] ve [7].

Trade-off. Permütasyonların aksine, start indeksi sıra yinelenmelerini önler.

Çözüm

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;
}

Şablon bağlantısı

Yeniden kullanımlı backtracking.

Yansıma

Aynı sayı tekrar kullanılabilir ama sıra sabit: döngü i’den başlar. Bu permütasyonu keser.
Kalan 0 olunca kopyasını ekle. Aynı diziyi push edersen sonraki adım hepsini bozar.
Aşımda dal kesilir. Hedef 0 ve boş aday. Adaylar pozitif (garanti).