Eşit Toplamlı Bölüm Alt Kümesi
Bölümleme problemini toplamın yarısını hedefleyen bir 0/1 sırt çantası olarak yeniden ifade edin ve uygunluğu boole DP dizisiyle belirleyin.
Eşit Toplamlı Bölüm Alt Kümesi, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 3. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.
Problem Açıklaması
Boş olmayan bir pozitif tam sayılar dizisi nums verildiğinde, diziyi toplamları eşit iki alt kümeye ayırıp ayıramayacağınızı belirleyin. Örneğin [1, 5, 11, 5], her ikisinin toplamı 11 olacak şekilde [1, 5, 5] ve [11] olarak bölümlendirilebilir. Toplam çift değilse yanıt hemen False olur. Aksi takdirde, toplamın total_sum // 2 değerine eşit olduğu bir alt küme bulmamız gerekir; bu, klasik bir alt küme toplamı problemidir.
Alt Küme Toplamına İndirgeme
Temel indirgeme şudur: tüm elemanların toplamı S çiftse ve bir alt kümenin toplamı S//2 ise kalan elemanların toplamı da otomatik olarak S//2 olur. Dolayısıyla Eşit Toplamlı Alt Kümelere Bölme, sayı dizisindeki herhangi bir alt kümenin toplamının S//2 olup olmadığı sorusuna indirgenir. Bu, klasik NP-tam Alt Küme Toplamı problemidir ve problemi 0/1 sırt çantası DP'siyle O(n × S) zamanında çözeriz.
def canPartition(nums):
total = sum(nums)
if total % 2 != 0:
return False # odd sum: impossible
target = total // 2
# Now: does any subset of nums sum to target?Mantıksal DP Dizisi
dp[c] adlı bir mantıksal dizi tanımlayın; dp[c] = True, toplamı tam olarak c olan bir alt kümenin bulunduğu anlamına gelir. dp[0] = True değerini başlatın (boş alt kümenin toplamı 0'dır) ve diğer tüm değerleri False yapın. Her num sayısı için kapasiteyi target değerinden num değerine kadar geriye doğru dolaşın (0/1 sırt çantasında geriye doğru dolaşma) ve dp[c] = dp[c] or dp[c - num] değerini atayın.
def canPartition(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for c in range(target, num - 1, -1): # backward: 0/1 knapsack
dp[c] = dp[c] or dp[c - num]
return dp[target]
print(canPartition([1, 5, 11, 5])) # True
print(canPartition([1, 2, 3, 5])) # FalseÖrneği Adım Adım İzleme
[1, 5, 11, 5] için toplam=22, hedef=11'dir. Başlangıçta dp[0]=True olur. 1 sayısı işlendiğinde: dp[1]=True. 5 sayısı işlendiğinde: dp[5]=True, dp[6]=True. 11 sayısı işlendiğinde: dp[11]=True (yalnızca 11 kullanılarak). dp[11]=True değerini zaten bulduk; ancak tüm sayıları işlemeye devam ederiz. Sonuç: dp[11]=True, dolayısıyla bölme mümkündür.
Erken Sonlandırma İyileştirmesi
Erken bir çıkış ekleyebiliriz: herhangi bir anda dp[target] değeri True olursa hemen True döndürün. Bu, en iyi durum senaryolarını büyük ölçüde hızlandırabilir. Ayrıca tek bir eleman target değerine eşitse hemen True döndürebiliriz. Tek bir eleman target değerini aşarsa hedef toplamına ulaşan hiçbir alt kümede yer alamaz; ancak kalan elemanları yine de kontrol etmemiz gerekir.
def canPartition_fast(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
if max(nums) > target: # any element > target makes it impossible
return False
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for c in range(target, num - 1, -1):
dp[c] = dp[c] or dp[c - num]
if dp[target]:
return True # early exit
return dp[target]
print(canPartition_fast([1, 5, 11, 5])) # TrueDP Dizisi Yerine Python Kümesi Kullanma
Alternatif olarak ulaşılabilen toplamlar kümesini koruyabiliriz. {0} ile başlayın. Her sayı için, mevcut kümedeki her toplama bu sayıyı ekleyin: reachable = reachable | {s + num for s in reachable}. Yalnızca hedefi aşmayan toplamları tutacak şekilde filtreleyin. Sonunda target değerinin kümede olup olmadığını kontrol edin. Bu yaklaşım sezgiseldir; ancak daha fazla bellek kullanabilir ve uygulamada daha yavaş olabilir.
def canPartition_set(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
reachable = {0}
for num in nums:
reachable = {s + num for s in reachable if s + num <= target} | reachable
return target in reachable
print(canPartition_set([1, 5, 11, 5])) # TrueKarmaşıklık Analizi
DP yaklaşımı, S = sum(nums) olmak üzere O(n × S) zamanında çalışır ve mantıksal dizi için O(S) alan kullanır. LeetCode kısıtlarında (n ≤ 200, toplam ≤ 20.000) bu en fazla 4.000.000 işlem demektir; yani oldukça hızlıdır. Küme yaklaşımı aynı asimptotik karmaşıklığa sahiptir; ancak küme oluşturmanın ek yükü nedeniyle uygulamada daha yavaş olabilir.
Genelleme: Toplamı Verilen Alt Kümeleri Sayma
Bununla ilişkili bir problem, toplamı hedefe eşit olan alt kümelerin sayısını bulmaktır. DP'yi mantıksal yapıdan tamsayı yapısına dönüştürün: dp[c] = number of ways to reach sum c. OR yerine toplama kullanın: dp[c] += dp[c - num]. dp[0] = 1 olarak başlatın. Aynı geriye doğru dolaşmayı kullanın. Bu genelleme, sırt çantası şablonunun alt kümelerle ilgili farklı sorulara nasıl uyarlandığını gösterir.
def count_subsets(nums, target):
dp = [0] * (target + 1)
dp[0] = 1
for num in nums:
for c in range(target, num - 1, -1):
dp[c] += dp[c - num]
return dp[target]
print(count_subsets([1, 1, 1, 1, 1], 3)) # 10 (C(5,3))Yaygın Mülakat Takip Soruları
Şu takip sorularını bekleyin: (1) Gerçek bölmeyi döndürmeniz gerekirse ne olur? — yeniden oluşturma için 2B DP gerekir. (2) Elemanlar negatif olabilirse ne olur? — hedefi öteleyin veya dizi yerine sözlük kullanın. (3) Zaman karmaşıklığı nedir? — O(n × toplam). (4) Sayıların çoğu aynıysa iyileştirme yapabilir misiniz? — evet, dış döngüdeki yineleme sayısını azaltmak için frekans sayımı kullanın. Bu ödünleşimleri her zaman önceden belirtin.
0/1 Sırt Çantasıyla Bağlantı Kurma
Eşit Toplamlı Alt Kümelere Bölme, 0/1 sırt çantasının doğrudan bir uygulamasıdır: ögeler sayılardır, ağırlıklar değerlere eşittir ve sırt çantasının kapasitesi hedefe eşittir. Maksimum değerin hedefe eşit olup olmadığını sorarız (uygulanabilirlik); maksimum değerin ne olduğunu sormayız. Geriye doğru dolaşma aynıdır; yalnızca işlem max değerinden mantıksal or değerine değişir. Bir mülakatta bu bağlantıyı fark etmek, güçlü örüntü tanıma becerisi gösterir.
Sınır Durumları
Ele alınması gereken sınır durumları: (1) uzunluğu 1 olan dizi — tek eleman bölünemez, sonuç her zaman False olur; (2) tüm elemanlar aynı ve eleman sayısı çiftse — tek tek değerlerine bağlı olarak sonuç mümkün olabilir veya olmayabilir; (3) çok büyük toplamlar — DP dizisini ayırmadan önce kısıtları kontrol edin; (4) hedeften büyük elemanlar — hedef toplamına ulaşan bir alt kümenin parçası olamayacakları için atlanabilirler. Maksimum eleman kontrolünü erken çıkış olarak kullanmak, (4) numaralı durumu verimli biçimde ele alır.
Hızlı Kontrol
Bu dersteki Veri Yapıları & Algoritmalar — Kodlama Mülakatına Hazırlık kavramlarını anlayışınızı sınayın.
Ders Özeti
Bu derste şunları öğrendiniz: Eşit Toplamlı Alt Kümelere Bölme, hedef = toplam//2 olan alt küme toplamı problemine indirgenir, mantıksal 1B DP dp[c], 0/1 sırt çantasıyla aynı geriye doğru dolaşmayı kullanır ve mantıksal OR işlemi tamsayı toplamayla değiştirilerek yaklaşım alt kümeleri sayacak şekilde genellenebilir. Sırada, işaret atamalarını alt küme toplamı farkı üzerinde bir sırt çantası problemine dönüştürerek Hedef Toplam problemine geçiyoruz.
Sıkça Sorulan Sorular
“Eşit Toplamlı Bölüm Alt Kümesi” dersi ücretsiz mi?
Evet — “Eşit Toplamlı Bölüm Alt Kümesi” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.
“Eşit Toplamlı Bölüm Alt Kümesi” dersinde ne öğreneceğim?
Bölümleme problemini toplamın yarısını hedefleyen bir 0/1 sırt çantası olarak yeniden ifade edin ve uygunluğu boole DP dizisiyle belirleyin. Coding Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 3. dersidir.
“Eşit Toplamlı Bölüm Alt Kümesi” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Coding Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- 0/1 Sırt Çantası ve Alan Optimizasyonu
- Sınırsız Sırt Çantası ve Bozuk Para Değişimi II
- Eşit Toplamlı Bölüm Alt Kümesi
- Pozitif ve Negatif İşaretlerle Hedef Toplam