Subsets

+10

Birbirinden farklı tam sayılardan oluşan nums listesini alırsın. Boş küme ve listenin tamamı dâhil olmak üzere, bu listenin tüm alt kümelerini döndür; n değer 2^n alt küme verir. Her alt kümeyi değerleri artan sırada olacak şekilde yaz ve alt kümeleri sözlük sırasına göre listele: iki alt kümeyi değer değer karşılaştır; ilk farklılık sonucu belirler ve başka bir alt kümenin başlangıcı olan alt küme önce gelir. [1, 2] için yanıt [[], [1], [1, 2], [2]] olur.

Fonksiyon

subsets(nums: integer-array) → integer-2d-array

numsinteger-array: değerlerin tümü farklı, herhangi bir sırada
Döndürürinteger-2d-array: her alt küme artan sırada sıralanmış, alt kümeler sözlük sırasına göre listelenmiş

Kısıtlar

1 ≤ nums.length ≤ 10
-10 ≤ nums[i] ≤ 10
nums içindeki tüm değerler farklıdır.
nums herhangi bir sırada gelebilir.

Örnekler

Girdi: nums = [3, 1, 2]
Çıktı: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
Açıklama: Sıralandığında değerler 1, 2, 3'tür ve üç değer 2^3 = 8 alt küme verir. [1, 2], başlangıcı olduğu için [1, 2, 3]'ten önce gelir; [1, 2, 3] ise ikinci konumda 2, 3'ten küçük olduğu için [1, 3]'ten önce gelir.

Girdi: nums = [0]
Çıktı: [[], [0]]
Açıklama: Bir değerin iki alt kümesi vardır: onu dışarıda bırakıp [] elde edin ya da onu alıp [0] elde edin. Boş alt küme her zaman önce gelir.

Girdi: nums = [5, -2]
Çıktı: [[], [-2], [-2, 5], [5]]
Açıklama: Değerler -2 ve 5 olarak sıralanır, bu nedenle [-2, 5] bu sırayla yazılır. -2 içeren her alt küme, -2 5'ten küçük olduğu için [5] kümesinden önce gelir.

Gönderirken +13 gizli test

Ek soru

Her alt kümeyi bir öncekinden doğrudan oluşturarak, yinelemeli çağrı kullanmadan aynı listeyi oluşturabilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

2^n alt küme vardır; bu nedenle hiçbir yöntem O(2^n) işlemden daha azını yapamaz. Asıl soru, sonradan 1024 listeyi sıralamadan, her alt kümeyi istenen sırada bir kez nasıl üreteceğimizdir. Sıralanmış değerler üzerinde geri izleme yapıp karar ağacının her düğümünü ona girerken kaydetmek, alt kümeleri tam olarak sözlük sırasıyla dolaşır.

Bit maskeleri, ardından sıralama

Sezgi

Sıralanmış değerleri 0 ile n-1 arasındaki konumlara yerleştir. Bir alt küme, her konum için evet ya da hayır der; bir sayının n biti de bunu yapar. Dolayısıyla 0 ile 2^n-1 arasındaki sayılar alt kümelerdir: [1, 2, 3] için 5 maskesi ikilik sistemde 101'dir, 0. ve 2. bitler açıktır ve [1, 3] alt kümesini temsil eder. 0 maskesi boş alt küme, 7 maskesi ise listenin tamamıdır.

Farklı maskeler farklı alt kümeler verir ve her alt kümenin bir maskesi vardır; bu nedenle döngü, 2^n alt kümenin tümünü tam olarak bir kez üretir. Bitleri sıralanmış değerler üzerinde 0. konumdan başlayarak okumak, her alt kümeyi artan sırada yazar.

Maskeler, problemin istediği sırada gelmez. 1 maskesi [1], 2 maskesi [2] ve 3 maskesi [1, 2] olduğundan, [2] değeri [1, 2] değerinden önce gelir. Bunu, değerleri tek tek karşılaştıran ve öneki önceye koyan bir karşılaştırıcıyla sıralama yaparak düzeltirsin. Sıralama, üretimden daha fazla maliyetlidir: 2^n alt küme yaklaşık n × 2^n karşılaştırma gerektirir ve her karşılaştırma en fazla n değer okur. n = 10 için bu yaklaşık 10^5 okuma demektir; yine de hızlıdır, ancak sonraki yaklaşımın hiç yapmadığı bir iştir.

Algoritma

nums dizisini her alt küme artan sırada okunacak şekilde sırala.
0'dan 2^n-1'e kadar her maske için, biti 1 olan konumlardaki değerleri topla.
Alt kümeler listesini sırala: İki alt kümenin farklı olduğu ilk konumda, daha küçük değer önce gelir; biri önce tükenirse, o önce gelir.
Sıralanmış listeyi döndür.

def subsets(nums):
    values = sorted(nums)
    n = len(values)
    result = []
    for mask in range(1 << n):
        # Bit i of mask says whether values[i] is in this subset.
        result.append([values[i] for i in range(n) if (mask >> i) & 1])
    # Python compares lists position by position, and a prefix comes first.
    result.sort()
    return result

Geri izleme: seç, keşfet, seçimi geri al

Sezgi

Alt kümeleri bir ağaç olarak düşünün. Kök, boş alt kümedir. Bir düğümün altına, eklediğiniz son değerden büyük olan herhangi bir değeri ekleyebilirsiniz. Sıralanmış değerler [1, 2, 3] için kökün çocukları [1], [2] ve [3] olur; [1] düğümünün çocukları [1, 2] ve [1, 3] olur; [1, 2] düğümünün çocuğu ise [1, 2, 3] olur. Her alt küme bu ağaçta tam olarak bir kez yer alır; çünkü onu artan sırada yazmanın tek bir yolu vardır ve yalnızca yapraklar değil, her düğüm bir yanıttır.

Geri izleme, tek bir paylaşılan liste olan path ile ağaçta ilerler. Bir çocuğa inmek için seçim yaparsınız: değeri sona ekleyin. Ardından keşfedersiniz: yineleme yaparsınız ve yardımcı işlev, ulaştığı anda path listesinin bir kopyasını kaydeder. Sonra seçimi geri alırsınız: değeri kaldırırsınız; böylece path ebeveyn düğümüne döner ve sıradaki kardeş denenebilir. Her düğüm içeri girilirken kaydedildiğinden, ebeveyn her zaman çocuklarından önce yazılır.

Çıktının sıralama yapmadan sözlükbilimsel düzende olmasının nedeni budur. Bir düğümün çocukları en küçük değerden başlayarak denenir ve sonraki dala geçmeden önce mevcut dalın tamamı dolaşılır. [1, 2, 3] için şu değerler kaydedilir: [], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]: sözlük sıralamasında olduğu gibi, bir önek genişletilmiş hâllerinden önce gelir.

Ağaçta 2^n düğüm vardır ve bir yolu kopyalamak en fazla n maliyetlidir; bu nedenle süre, yanıtın kendi boyutu olan O(n × 2^n) olur. Çıktıya ek olarak, ikisi de en fazla n derinliğinde olan bir yol ve bir çağrı yığını tutulur.

Algoritma

Değerleri sırala.
explore(start) yaz. Önce path'in bir kopyasını sonuca ekler.
Ardından, start değerinden sona kadar her i indeksi için: values[i] değerini path'e ekle (seç), explore(i+1) çağrısını yap (keşfet) ve son değeri kaldır (seçimi geri al).
Boş bir path ile explore(0) çağrısını yap ve sonucu döndür.

def subsets(nums):
    values = sorted(nums)
    result = []
    path = []

    def explore(start):
        # Every node of the decision tree is a subset: record it on the way in.
        result.append(path[:])
        for i in range(start, len(values)):
            path.append(values[i])  # choose
            explore(i + 1)          # explore: only larger values may follow
            path.pop()              # un-choose

    explore(0)
    return result

Tuzaklar ve uç durumlar

Buradaki yanlış yanıtların çoğu sıralamadan ya da tek bir listenin paylaşılmasından kaynaklanır.

Bir kopyası yerine doğrudan path eklemek. Böylece her girdi aynı listeyi gösterir; yürüyüş bittiğinde liste boş olduğundan [] listesinin 2^n kopyasını döndürürsünüz.
nums listesini sıralamayı unutmak. [3, 1, 2] ile ağaç [3, 1] oluşturur; bu artan sırada değildir ve yürüyüş artık sözlük sırasına göre olmaz.
Permütasyonlarda yapacağınız gibi yalnızca yapraklarda kayıt tutmak. Bu ağacın her düğümü bir alt kümedir; yalnızca sona ulaşan yolları kaydetmek çok az alt küme döndürür.
i+1 yerine start+1 ile özyineleme yapmak. Böylece bir değer daha büyük bir değerin ardından, hatta kendisinin ardından gelebilir ve artan sırada alt kümeler olmayan [3, 2] ve [3, 3] gibi listeler elde edersiniz.
Dahil etme veya hariç tutma ağacını kullanıp (önce 0 değerine, sonra 1 değerine ve bu şekilde devam ederek karar verin) yaprakları kaydetmek. Bu yöntem 2^n alt kümenin tümünü bulur, ancak önce dahil etmeyi denemek tam listeyi ilk sıraya koyar; önce hariç tutmayı denemek ise [3] listesini [2] listesinden önce koyar. İkisi de sözlük sırasına uymaz.
Önce uzunluğa göre sıralayan bir karşılaştırıcı şu sıralamayı verir: [], [1], [2], [3], [1, 2]. Bu farklı bir sıralamadır.

Sıkça sorulan sorular4

n elemanlı bir kümenin kaç alt kümesi vardır?

2^n. Her öğe, diğerlerinden bağımsız olarak ya kümede bulunur ya da bulunmaz; dolayısıyla seçenekler çarpılır: ilk öğe için iki, ikinci öğe için iki ve böyle devam eder. Üç değer 8 alt küme, on değer ise boş alt küme ve kümenin tamamı da dahil olmak üzere 1024 alt küme verir.

Alt Kümeler probleminin zaman karmaşıklığı nedir?

O(n × 2^n). 2^n alt küme vardır ve bunlardan birini yazmak n adıma kadar sürer; bu nedenle yanıtı döndürmek bile bu kadar maliyetlidir. Geri izleme bu sınıra ulaşır ve yalnızca O(n) ek alan kullanır. Bit maskeleriyle üretmek aynı hızdadır, ancak sonucu sonradan sıralamak ek bir n çarpanı getirir.

Alt kümeler için geri izleme mi yoksa bit maskeleri mi kullanmalıyım?

Bit maskeleri kısadır, özyineleme gerektirmez ve dahil etme ya da etmeme seçimini bitler olarak görünür kılar. Geri izleme, alt kümeleri kendiliğinden sözlük sırasına göre verir ve yaygın varyantlara uyarlanabilir: yinelenen değerleri atlama, yalnızca k boyutundaki alt kümeleri seçme veya yalnızca hedef toplama ulaşan alt kümeleri seçme; bu durumda bir dalı keşfetmeyi erkenden durdurabilirsiniz.

Subsets'te yinelenen değerleri nasıl ele alırsınız?

Değerleri sıralayın, ardından geri izleme yardımcı işlevinin döngüsünde aynı düzeyde kendisinden önceki değere eşit olan bir değeri atlayın: i > start ve values[i] == values[i-1]. İlk kopya, onu kullanan tüm alt kümeleri zaten araştırır; bu nedenle ikinci kopyayla başlayan bir kardeş dalı aynı alt kümeleri yeniden oluşturur.

Python

def subsets(nums):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

nums = [3, 1, 2]

Beklenen

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]