Partition Equal Subset Sum

Q: Eşit Alt Kümelere Bölme Toplamı neden 0/1 sırt çantası problemidir?

target = total / 2 boyutunda bir sırt çantanız var ve her değeri en fazla bir kez kullanarak çantayı tam olarak doldurmalısınız. Bir değeri almak ya da almamak, 0/1 seçimidir ve bir değerin boyutu, değerin kendisidir. Ulaşılabilir toplamları gösteren sırt çantası tablosu, soruyu O(n × target) zamanda yanıtlar.

Q: Eşit Toplamlı Alt Küme Bölümleme probleminin zaman karmaşıklığı nedir?

Tablo yaklaşımı, target toplamın yarısı olmak üzere O(n × target) zaman ve tek satırla O(target) bellek gerektirir. En fazla 100 olan 200 değer için bu, yaklaşık 2 × 10^6 adımdır. Sınır yalnızca değerlerin sayısıyla değil, büyüklükleriyle de artar; bu nedenle sözde polinom olarak adlandırılır: 10^9'a yakın değerlerle hiçbir tablo sığmaz ve genel problem NP-tamdır.

OrtaDinamik programlama

+10

Pozitif tam sayılardan oluşan bir nums dizisi veriliyor. Değerleri toplamları eşit olan iki gruba ayırıp ayıramayacağını belirle. Her değer tam olarak bir gruba girer ve bir grup herhangi bir konumdaki değerleri alabilir. Böyle bir ayırma mümkünse true, değilse false döndür.

Fonksiyon

canPartition(nums: integer-array) → boolean

numsinteger-array: pozitif değerleri iki gruba ayırmak için
Döndürürboolean: Değerler toplamları eşit olan iki grup oluşturabiliyorsa true, aksi takdirde false

Kısıtlar

1 ≤ nums.length ≤ 200
1 ≤ nums[i] ≤ 100

Örnekler

Girdi: nums = [6, 1, 4, 9, 2]
Çıktı: true
Açıklama: Toplam 22 olduğuna göre her grubun 11 olması gerekir. 9 + 2 ve 6 + 1 + 4 gruplarının ikisi de 11 eder, bu nedenle yanıt true.

Girdi: nums = [4, 7, 2, 9, 6]
Çıktı: false
Açıklama: Toplam 28 olduğuna göre her grupta 14 olmalı. 9 tane olan gruba 5 tane daha gerekir ve 4, 7, 2 ve 6'dan oluşan hiçbir kombinasyon 5 etmediği için, toplam çift olmasına rağmen cevap false.

Girdi: nums = [1, 2, 3, 5]
Çıktı: false
Açıklama: Toplam 11'dir. Eşit iki tam sayı her zaman çift bir sayıya eşit olur; bu nedenle tek bir toplam asla bölüştürülemez ve yanıt false olur.

Gönderirken +18 gizli test

Ek soru

Eşit bir bölme mümkün olmadığında, iki grubun toplamları arasındaki mümkün olan en küçük farkı döndürebilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Her grup toplamın tam olarak yarısını içermelidir; dolayısıyla asıl soru, nums dizisinin herhangi bir alt kümesinin toplamının target = total / 2 olup olmadığıdır. Tüm alt kümeleri denemek 2^n işlem gerektirir; bu, 200 değer için uygulanabilir değildir. Ancak toplamların kendileri küçüktür: target en fazla 200 × 100 / 2 = 10^4 olur. Hangi toplamların elde edilebildiğini her seferinde bir değer ekleyerek kaydetmek, aramayı O(n × sum) adımda doldurulan bir 0/1 sırt çantası tablosuna dönüştürür.

Özyineleme kullanarak her alt kümeyi dene

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Toplamla başla. Tekse bölme mümkün değildir; çünkü iki eşit tam sayının toplamı çift sayıdır. Aksi hâlde her grubun tam olarak target = total / 2 değerine ulaşması gerekir. target değerini oluşturan değerleri bulduğunda, seçmediklerin diğer yarıyı kendiliğinden oluşturur. Dolayısıyla tek bir soruyu yanıtlamak yeterlidir: Herhangi bir alt küme target değerine ulaşabiliyor mu?

Değerleri sırayla dolaş ve her biri için bir seçim yap: onu ilk gruba koy ya da ikinci grup için bırak. reach(i, remaining) yardımcı işlevi, i indeksinden itibaren kalan değerlerin remaining değerini oluşturup oluşturamayacağını yanıtlar. remaining 0 olduğunda true, değerler tükendiğinde veya 0'ın altına düştüğünde false döndürür; aksi hâlde nums[i] için iki seçeneği de dener.

Her alt küme bir seçim yoluna karşılık gelir; bu nedenle arama hiçbir bölmeyi gözden kaçıramaz ve yanıt doğrudur. Ancak yavaştır, çünkü 2^n yol vardır ve bölmenin mümkün olmadığı bir girdi, neredeyse hepsini denemeye zorlar. 100 değerinin 199 kopyasını ve bir tane 98'i ele alalım: toplam 19998, hedef 9999'a hiçbir zaman ulaşılamaz ve arama yüzlüklerden en fazla 99 tanesini seçmenin tüm yollarını dener; bu da yaklaşık 4 × 10^59 yoldur. 40 değer bile 2^40, yani yaklaşık 10^12 yol demektir.

Algoritma

nums değerlerini topla. Toplam tekse false döndür.
target değerini toplamın yarısı olarak ayarla.
reach(i, remaining) fonksiyonunu yaz: remaining 0 olduğunda true, i son değeri geçtiğinde veya remaining 0'ın altına düştüğünde false döndür.
Aksi takdirde reach(i+1, remaining-nums[i]) veya reach(i+1, remaining) döndür: değeri al ya da alma.
reach(0, target) döndür.

def canPartition(nums):
    total = sum(nums)
    if total % 2 == 1:
        return False

    # Can some of the values from index i on add up to exactly remaining?
    def reach(i, remaining):
        if remaining == 0:
            return True
        if i == len(nums) or remaining < 0:
            return False
        # Put nums[i] in the first group, or leave it for the second one
        return reach(i + 1, remaining - nums[i]) or reach(i + 1, remaining)

    return reach(0, total // 2)

Bir tabloyu değer ve toplamla doldur

Sezgi

Özyineleme aynı soruyu tekrar tekrar sorar. reach(i, remaining) yalnızca iki sayıya bağlıdır: 0 ile n arasındaki i ve 0 ile target arasındaki remaining. Bu da en fazla (n+1) × (target+1) farklı soru demektir; sınır değerlerinde yaklaşık 201 × 10001 ≈ 2 × 10^6 soru eder ve her birini bir kez yanıtlamak için yeterince azdır.

Yanıtları bir tabloda ileriye doğru oluştur. can[i][s], ilk i değerden bazılarının toplamının s olup olmadığını belirtir. Hiç değer yokken yalnızca 0 toplamı mümkündür; bu nedenle 0. satırda can[0][0] dışında her şey false olur. num = nums[i-1] değeri, s değerine ulaşmanın iki yolunu verir: num değerini dışarıda bırakmak; böylece önceki değerlerin toplamı zaten s olur ya da onu dahil etmek; böylece önceki değerlerin toplamı s-num olur. Kuralın tamamı budur: can[i][s] = can[i-1][s] or can[i-1][s-num]; ikinci kısım yalnızca s ≥ num olduğunda hesaba katılır. Her satır yalnızca üstündeki satırı okur, bu nedenle her değer en fazla bir kez kullanılır.

Hedef 11 olduğunda [6, 1, 4, 9, 2] dizisinde ulaşılabilir toplamlar {0} kümesinden {0, 6} kümesine, ardından {0, 1, 6, 7} kümesine ve sonra {0, 1, 4, 5, 6, 7, 10, 11} kümesine genişler. 11 toplamına 4 değerinden sonra (6 + 1 + 4) ulaşılır ve sonraki satırlarda da bu değer korunur. Yanıt can[n][target] olur. Her hücre sabit miktarda işlem gerektirir; dolayısıyla hem zaman hem de bellek karmaşıklığı O(n × target) olur.

Algoritma

Toplam tek ise false döndür ve target değerini bunun yarısına ayarla.
n+1 satır ve target+1 sütundan oluşan, tüm değerleri false olan bir tablo oluştur ve can[0][0] değerini true olarak ayarla.
1'den n'ye kadar her i satırı için num = nums[i-1] değerini al.
0'dan target değerine kadar her s toplamı için can[i][s] değerini can[i-1][s] değerine veya s ≥ num olduğunda can[i-1][s-num] değerine ayarla.
can[n][target] değerini döndür.

def canPartition(nums):
    total = sum(nums)
    if total % 2 == 1:
        return False
    target = total // 2
    n = len(nums)

    # can[i][s] is True when some of the first i values add up to s
    can = [[False] * (target + 1) for _ in range(n + 1)]
    can[0][0] = True
    for i in range(1, n + 1):
        num = nums[i - 1]
        for s in range(target + 1):
            # Leave num out, or put it in and reach s - num with the values before it
            can[i][s] = can[i - 1][s] or (s >= num and can[i - 1][s - num])
    return can[n][target]

Yukarıdan aşağıya doldurulmuş bir toplama satırı

Sezgi

Tablonun her satırı yalnızca kendisinin üstündeki satırı okur; bu yüzden satırı yerinde güncellersen tek bir satır yeterlidir: reach[s], şimdiye kadar görülen değerlerden bazılarının toplamının s olup olmadığını belirtir. Tehlike, güncellemelerin sırasındadır. s değerini artırarak ilerlersen reach[s-num] aynı num tarafından zaten etkinleştirilmiş olabilir. [3, 9] ve hedef 6 için 3, reach[3] değerini işaretler, ardından iki tane 3'ün varmış gibi reach[6] değerini işaretlemek için onu okur ve var olmayan bir bölme için true yanıtını verirsin.

s değerinde, target değerinden num değerine doğru azalarak ilerle. Böylece s-num, bu değerin henüz dokunmadığı daha küçük bir indeks olur; dolayısıyla reach[s-num] hâlâ num gelmeden önceki yanıtı tutar. Bu tam olarak tablodaki can[i-1][s-num] değeridir ve tek satır tüm tablonun yaptığı işi yapar.

reach[target] true olduğu anda da durabilirsin; çünkü sonraki değerler yalnızca erişilebilir toplamlar ekler, hiçbirini kaldırmaz. En kötü durumda hâlâ O(n × target) adım gerekir; bu yaklaşık 2 × 10^6 adımdır ve bellek kullanımı target + 1 boole değerine düşer.

Algoritma

Toplam tek ise false döndür ve target değerini toplamın yarısına ayarla.
target + 1 öğeli bir reach dizisi oluştur; reach[0] dışındaki tüm öğeler false olsun.
Her num değeri için s değerini target değerinden num değerine doğru azaltarak ilerle ve reach[s-num] true olduğunda reach[s] değerini true yap.
Her değerden sonra, reach[target] true ise true döndür.
Döngü biterse, false olan reach[target] değerini döndür.

def canPartition(nums):
    total = sum(nums)
    if total % 2 == 1:
        return False
    target = total // 2

    # reach[s] is True when some of the values seen so far add up to s
    reach = [False] * (target + 1)
    reach[0] = True
    for num in nums:
        # Walk the sums downward so num is used at most once
        for s in range(target, num - 1, -1):
            if reach[s - num]:
                reach[s] = True
        if reach[target]:
            return True
    return reach[target]

Tuzaklar ve uç durumlar

Buradaki yanlış yanıtlar; açgözlü bir kurala güvenmekten, tek sayı kontrolünü atlamaktan ve tek satırlı tabloda bir değeri yeniden kullanmaktan kaynaklanır.

Tek satırlı sürümde toplamları yukarı doğru hesaplarken bir değer birden fazla kez kullanılır. [3, 9] için hedef 6'dır; 3, önce toplam 3'ü, sonra toplam 6'yı işaretler ve true yanıtını verirsiniz.
Tek sayı kontrolünü atlamak: [1, 2] için toplam 3, aşağı yuvarlanarak 1 hedefini verir; 1 değeri bu hedefe ulaşır ve var olamayacak bir bölme için true yanıtını verirsiniz.
Sıralayıp her zaman daha hafif gruba eklemek gibi açgözlü yerleştirme, [3, 3, 2, 2, 2] üzerinde başarısız olur: 5'e karşı 7'de biter; oysa 3 + 3 = 2 + 2 + 2.
[2, 2, 2, 10] örneğindeki gibi hedeften büyük bir değer. target değerinden num değerine doğru bir döngü sıfır kez çalışır; bu doğrudur, ancak R'deki (num+1):(target+1) gibi bir aralık geriye doğru sayar ve tabloyu bozar. Bu tür değerleri atlayın.
Toplamın çift olması yeterli değildir: [4, 7, 2, 9, 6] toplamı 28 eder ve yine de bölünemez.
Lua ve R dizileri 1'den başlar; bu nedenle s toplamına karşılık gelen girdi, s + 1 dizinindedir.

Sıkça sorulan sorular4

Eşit Alt Kümelere Bölme Toplamı neden 0/1 sırt çantası problemidir?

target = total / 2 boyutunda bir sırt çantanız var ve her değeri en fazla bir kez kullanarak çantayı tam olarak doldurmalısınız. Bir değeri almak ya da almamak, 0/1 seçimidir ve bir değerin boyutu, değerin kendisidir. Ulaşılabilir toplamları gösteren sırt çantası tablosu, soruyu O(n × target) zamanda yanıtlar.

Eşit Toplamlı Alt Küme Bölümleme probleminin zaman karmaşıklığı nedir?

Tablo yaklaşımı, target toplamın yarısı olmak üzere O(n × target) zaman ve tek satırla O(target) bellek gerektirir. En fazla 100 olan 200 değer için bu, yaklaşık 2 × 10^6 adımdır. Sınır yalnızca değerlerin sayısıyla değil, büyüklükleriyle de artar; bu nedenle sözde polinom olarak adlandırılır: 10^9'a yakın değerlerle hiçbir tablo sığmaz ve genel problem NP-tamdır.

İç döngü neden hedeften değere doğru ilerliyor?

Aşağı doğru ilerlemek, bu değerin değiştirebilmesinden önce reach[s-num] değerinin okunması demektir; dolayısıyla hâlâ num öncesindeki değerleri tanımlar. Yukarı doğru ilerlemek, num kullanılarak oluşturulmuş bir toplamın tekrar num eklenerek genişletilmesine yol açar; bu da bir değerin birçok kez sayılmasına neden olur. Sınırsız kopyalar için, Coin Change'de olduğu gibi, yukarı döngü doğrudur; burada ise yanlıştır.

Partition Equal Subset Sum problemi bir bitset ile çözülebilir mi?

Evet. Ulaşılabilir toplamları, yalnızca 0. biti ayarlanmış olarak başlayıp büyük bir sayının bitleri şeklinde sakla. Her değer için bits |= bits << num, bu değeri tüm ulaşılabilir toplamlarına aynı anda ekler ve yanıt, target bitinin ayarlanmış olup olmadığıdır. Bu, aynı tablodur; ancak her makine sözcüğü aynı anda 64 toplamı işler, bu nedenle uygulamada çok daha hızlı çalışır.

Python

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

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

nums = [6, 1, 4, 9, 2]

Beklenen

true

Partition Equal Subset Sum

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Özyineleme kullanarak her alt kümeyi dene

Bir tabloyu değer ve toplamla doldur

Yukarıdan aşağıya doldurulmuş bir toplama satırı

Tuzaklar ve uç durumlar

Sıkça sorulan sorular4

Benzer problemler