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 II

Problem (yeniden ifade)

Yinelenen içerebilen bir tamsayı dizisinin tüm benzersiz alt kümelerini döndür.

Sezgi

Subsets ile aynı güç kümesi DFS’i, ama önce sırala ve aynı derinlikte eşit kardeşleri atla.

Yaklaşımlar

Sırala + yinelenenleri atla

Doğrulanmadı

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

Fikir. Sırala; start i’de, nums[i]==nums[i-1] ve i>start ise continue (aynı seçim zaten keşfedildi).

Yürüyüş. [1,2,2] → [], [1], [1,2], [1,2,2], [2], [2,2] - yinelenen [1,2] yok.

Trade-off. Yalnızca aynı seviyede atlamak, ardışık alımlarla çok kopyalı alt kümeleri korur.

Çözüm

export function subsetsWithDup(nums: number[]): number[][] {
  nums = [...nums].sort((a, b) => a - b);
  const res: number[][] = [];
  const path: number[] = [];
  const dfs = (start: number) => {
    res.push([...path]);
    for (let i = start; i < nums.length; i++) {
      if (i > start && nums[i] === nums[i - 1]) continue;
      path.push(nums[i]!);
      dfs(i + 1);
      path.pop();
    }
  };
  dfs(0);
  return res;
}

export function subsetsWithDup(nums: number[]): number[][] {
  nums = [...nums].sort((a, b) => a - b);
  const res: number[][] = [];
  const path: number[] = [];
  const dfs = (start: number) => {
    res.push([...path]);
    for (let i = start; i < nums.length; i++) {
      if (i > start && nums[i] === nums[i - 1]) continue;
      path.push(nums[i]!);
      dfs(i + 1);
      path.pop();
    }
  };
  dfs(0);
  return res;
}

Şablon bağlantısı

Yinelenen budamalı backtracking (Combination Sum II gibi).

Yansıma

Önce sırala. Aynı derinlikte nums[i] == nums[i-1] ise atla. Bu yinelenen alt kümeyi keser.
Daha derin indekste aynı değeri almak serbest: [1,2,2] içinde iki 2.
Hepsi eşit. Boş dizi: [[]]. Sıralamazsan atlama kuralı çalışmaz.