Tüm alt kümeler

Problem

Elemanları birbirinden farklı bir tamsayı dizisi veriliyor. Dizinin tüm alt kümelerini (boş küme ve dizinin kendisi dahil) döndür. Aynı alt küme iki kez yer almamalı; alt kümelerin ve içlerindeki elemanların sırası serbest.

Girdi: [4, 7, 9]
Çıktı (bu çözümün sırası):
[], [4], [4, 7], [4, 7, 9], [4, 9], [7], [7, 9], [9]

Girdi: []    -> [[]]
Girdi: [-1]  -> [[], [-1]]

n elemanlı bir kümenin 2ⁿ alt kümesi vardır; çıktının kendisi üstel büyüklüktedir.

Netleştirme soruları

• Elemanlar benzersiz mi? (Evet. Tekrar olsaydı problem Subsets II olurdu ve tekrar eden alt kümeleri ayıklamak gerekirdi.)
• Çıktı sırası önemli mi? (Hayır; ama testlerin buna göre yazılması gerekir.)
• n en fazla kaç? (LeetCode'da 10. n = 30 olsaydı 10⁹ alt küme belleğe sığmazdı; bu soru çıktı boyutunu konuşturur.)
• Sonuç liste olarak mı dönmeli, yoksa her alt küme bir callback'e mi verilebilir?

İpuçları

Yaklaşım

Iteratif kurma: Sonucu [[]] ile başlat; her yeni eleman için mevcut tüm alt kümelerin bu elemanı eklenmiş kopyalarını sonuca ekle. Basit ve özyinelemesizdir.

Bit maskesi: 0'dan 2ⁿ - 1'e kadar her sayı bir alt kümeyi temsil eder; i'nci bit 1 ise i'nci eleman alt kümededir. n ≤ 30 için int, n ≤ 62 için long yeterlidir (ama çıktı zaten o kadar büyük olamaz). Testlerde referans olarak kullanıldı.

Backtracking (seçilen çözüm): backtrack(start, current):

1. current'ın kopyasını sonuca ekle.
2. i = start..n-1 için: nums[i]'yi ekle, backtrack(i + 1, current), sonra çıkar.

Neden tekrar yok? Her alt küme, elemanları artan indeks sırasıyla eklenerek tam olarak bir yoldan üretilir; i + 1'den devam etmek, daha önceki bir elemanın sonradan eklenmesini engeller.

Backtracking bu soru için en kısa çözüm değildir, ama mülakatın asıl amacı şablonu göstermektir: Combination Sum, Permutations, N-Queens, Palindrome Partitioning aynı "seç, ilerle, geri al" iskeletini kullanır.

Java çözümü

import java.util.ArrayList;
import java.util.List;

public final class Subsets {

    /** Elemanlar birbirinden farklı. */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>(1 << nums.length);
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] nums, int start, List<Integer> current, List<List<Integer>> result) {
        result.add(new ArrayList<>(current));             // her düğüm bir alt küme: KOPYASINI ekle
        for (int i = start; i < nums.length; i++) {
            current.add(nums[i]);                         // seç
            backtrack(nums, i + 1, current, result);      // sadece sağdakilerle devam: tekrar yok
            current.remove(current.size() - 1);           // geri al
        }
    }
}

Sonuç listesi 1 << n kapasiteyle açıldı; boyut önceden bilindiği için yeniden boyutlandırma maliyeti olmaz. current.remove(current.size() - 1) indeksle silme yapar; List<Integer> üzerinde remove(Object) ile karışmaması için indeks ifadesi int olmalıdır. current.remove(nums[i]) yazmak, nums[i]'yi indeks olarak yorumlar; klasik bir Java tuzağı.

Karmaşıklık

• Zaman: O(n · 2ⁿ). 2ⁿ alt küme var ve her birinin kopyası ortalama n/2 eleman içerir.
• Bellek: Çıktı O(n · 2ⁿ). Çıktı hariç O(n) (özyineleme derinliği ve current listesi).

Çıktı boyutu kadar iş yapmak kaçınılmazdır; bu yüzden bu çözüm optimaldir.

Kenar durumlar ve testler

Testler main içinde çalıştırıldı:

• [4, 7, 9]: yukarıdaki sırayla 8 alt küme (tam sıra karşılaştırması).
• Boş dizi: [[]] (boş küme her zaman vardır).
• Tek eleman: [[], [-1]].
• n = 0..10 için: sonuç boyutu 2ⁿ ve alt küme kümesi (sıradan bağımsız, her alt küme sıralanarak) bit maskesi referansıyla birebir aynı.

Sıra serbest olduğunda test, beklenen ve gerçek sonucu normalleştirip (sıralayıp kümeye çevirip) karşılaştırmalıdır; aksi halde doğru ama farklı sırada üreten bir çözüm haksız yere başarısız olur.

Mülakatçı için

Bu soru backtracking şablonunun temizliğini ölçer. Gözlemle: aday "seç, devam et, geri al" yapısını net kuruyor mu? Sonuca kopya ekliyor mu (new ArrayList<>(current))? start indeksiyle tekrarı nasıl önlediğini açıklayabiliyor mu? Zaman karmaşıklığında çıktı boyutunu hesaba katıyor mu (sadece "O(2ⁿ)" demek eksiktir)?

İpucu zamanlaması: Bu soru 15 dakikalık bir sorudur; aday 3 dakikada bir yaklaşım bulamazsa ilk ipucunu ver. Kopya almayı unutan aday çıktıda boş listeler görür; hatayı söyleme, küçük bir dry run ile bulmasını bekle. Bit maskesi çözümünü kendiliğinden öneren aday ekstra sinyal verir.

Takip sorusu 1: Dizide tekrar eden elemanlar var ([1, 2, 2]); tekrar eden alt kümeleri üretme. Beklenen: diziyi sırala; döngüde i > start && nums[i] == nums[i-1] ise atla. Böylece aynı değer aynı derinlikte sadece bir kez seçilir (LeetCode 90).

Takip sorusu 2: Sadece k elemanlı alt kümeleri döndür. Beklenen: current.size() == k olunca ekle ve dön; budama: kalan eleman sayısı yetmiyorsa (n - i < k - current.size()) döngüden çık (LeetCode 77).

Takip sorusu 3: n = 40 ve toplamı hedefe eşit bir alt küme var mı? Beklenen: 2⁴⁰ çok büyük; "meet in the middle": iki yarının alt küme toplamlarını ayrı ayrı (2 × 2²⁰) üretip birini sıralayıp diğerinden binary search. Toplamlar küçükse alt küme toplamı DP'si.

Benzer problemler

• Subsets II (LeetCode 90)
• Combinations (LeetCode 77)
• Permutations (LeetCode 46)
• Combination Sum (LeetCode 39)
• Letter Case Permutation (LeetCode 784)