Geri İzleme

Nasıl düşünülür

Her adımda bir seçim dene, özyinele, sonra geri al. Çağrı yığını güncel yoldur. Kısmi çözüm geçerli tamamlanmaya götüremezse buda. Yinelenen çıktıyı önlemek için seçim sırasına dikkat et.

Şablon şekilleri

Şekil	Temel hamle	Notlar
Alt kümeler	Her elemanı al veya atla	Her düğümde path kopyası
Permütasyonlar	Swap veya used[] maskesi	Uzunluk == n → kaydet
Kombinasyonlar	Başlangıç indeksi i	Yeniden sıralı yinelenenlerden kaçın

Karmaşıklık temeli

Çıktıya duyarlı: genelde O(n·#çözüm). Ekstra alan özyineleme derinliği O(n).

Şablondan probleme

1. Durumu tanımla (path, indeks, kalan hedef, used maskesi).
2. Temel durum: tam geçerli yolu kaydet.
3. Seçimleri döngüle; push; özyinele; pop.
4. Budama ekle (toplam fazla, hücre ziyaret, vb.).

/** Backtracking template: subsets (choose / skip via start index). */
export function subsets(nums: number[]): number[][] {
  const res: number[][] = [];
  const path: number[] = [];
  const dfs = (start: number) => {
    res.push([...path]);
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]!);
      dfs(i + 1);
      path.pop();
    }
  };
  dfs(0);
  return res;
}

/** Backtracking template: subsets (choose / skip via start index). */
export function subsets(nums: number[]): number[][] {
  const res: number[][] = [];
  const path: number[] = [];
  const dfs = (start: number) => {
    res.push([...path]);
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]!);
      dfs(i + 1);
      path.pop();
    }
  };
  dfs(0);
  return res;
}