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

Tested only

Time O(n * 2^n)Space 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.

Solution

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

Bu problemi 90 saniye içinde hangi kalıp ele verdi?
Standart şablondan ne değişti?
Mevcut çözümü ne bozar?