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

Subsets

Problem (yeniden ifade)

Ayrı tamsayılardan oluşan dizinin tüm alt kümelerini (güç kümesi) döndür.

Sezgi

Her indekste: atla veya al, sonra özyinele. Her düğümde yolu kaydet.

Yaklaşımlar

Dahil et / hariç tut DFS

Doğrulanmadı

Zaman O(n * 2^n)Alan O(n)

Fikir. dfs(i): yolu ekle; j>=i için nums[j]’yi al, dfs(j+1), geri al.

Adım adım. [1,2,3] → [] ve tam küme dahil 8 alt küme.

Ödünleşimler. Bit mask yinelemesi de O(n·2^n); şablon backtracking.

Çözüm

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

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

Şablon bağlantısı

Backtracking seç / keşfet / geri al.

Yansıma

Her indekste al veya alma. 2ⁿ yaprak. İndeks ilerlemesi aynı kümeyi permütasyon diye tekrarlamaz.
Cevaba dizinin kopyasını ekle. Aynı listeyi push edersen sonraki seçim eskileri de değiştirir.
Boş dizi: [[]].