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

Permutations

Problem (yeniden ifade)

Ayrı tamsayılardan oluşan bir liste verildiğinde tüm olası permütasyonları döndür.

Sezgi

Backtracking: kullanılmamış bir sayı seç, özyinele, geri al. Yol uzunluğu == n olunca bir kopya kaydet.

Yaklaşımlar

Kullanıldı bayraklı backtracking

Doğrulanmadı

Zaman O(n · n!)Alan O(n)

Fikir. path listesi + used boolean dizisi. Her kullanılmamış indeksi dene, özyinele, pop.

Yürüyüş. [1,2,3] 6 permütasyonu keşfeder.

Trade-off. Swap tabanlı yerinde üretim path için daha az yardımcı bellek kullanır ama okunması daha zor.

Çözüm

export function permute(nums: number[]): number[][] {
  const res: number[][] = [];
  const path: number[] = [];
  const used = new Array(nums.length).fill(false);
  const dfs = () => {
    if (path.length === nums.length) { res.push([...path]); return; }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true; path.push(nums[i]!);
      dfs();
      path.pop(); used[i] = false;
    }
  };
  dfs();
  return res;
}

export function permute(nums: number[]): number[][] {
  const res: number[][] = [];
  const path: number[] = [];
  const used = new Array(nums.length).fill(false);
  const dfs = () => {
    if (path.length === nums.length) { res.push([...path]); return; }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true; path.push(nums[i]!);
      dfs();
      path.pop(); used[i] = false;
    }
  };
  dfs();
  return res;
}

Şablon bağlantısı

Seç / keşfet / geri al. saf backtracking şablonu.

Yansıma

used[i] seçileni atlar. Yaprak sayısı n!. Geri alırken bayrağı temizlemezsen kardeş dal eksik kalır.
Yinelenen değer yok. Swap-back aynı ağacı üretir.
Tek eleman bir permütasyon. Boş dizi: bir boş cevap.