Subset Sum Problem
nums pozitif tam sayıları içerir ve target pozitif bir tam sayıdır. Her konumu en fazla bir kez kullanarak değerlerden bazılarını seçip toplamlarının tam olarak target olmasını sağlayabilir misin? Mümkünse true, hiçbir seçim işe yaramıyorsa false döndür.
Fonksiyon
- numsinteger-array
- seçebileceğiniz pozitif değerler
- targetinteger
- seçilen değerlerin ulaşması gereken tam toplam
- Döndürürboolean
- Değerlerden bazıları toplamda tam olarak target değerini veriyorsa true, aksi takdirde false
Kısıtlar
1 ≤ nums.length ≤ 2001 ≤ nums[i] ≤ 1041 ≤ target ≤ 104
Örnekler
- Girdi
- nums = [8, 3, 11, 5, 7]target = 15
- Çıktı
- true
- Açıklama
- 8 + 7 = 15, yani cevap
true. 3 + 5 + 7 seçimi de işe yarar; bir seçim yeterlidir.
- Girdi
- nums = [6, 9, 12, 15]target = 20
- Çıktı
- false
- Açıklama
- Her değer 3'ün katıdır, bu yüzden bunların toplamı da 3'ün katıdır. 20 ise 3'ün katı değildir, dolayısıyla yanıt
false.
- Girdi
- nums = [4, 1, 2]target = 8
- Çıktı
- false
- Açıklama
- Üç değerin toplamı 4 + 1 + 2 = 7 eder; bu da 8'den küçüktür, dolayısıyla hiçbir seçim bu değere ulaşamaz ve yanıt
falseolur.
Ek soru
Farklı konumlardaki iki eşit değer, farklı seçimler sayılır. target değerine ulaşan kaç seçim vardır?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
nums[0]ile başla. Seçimin bunu içeriyorsa, diğer değerlerin toplamıtarget-nums[0]olmalıdır. İçermiyorsa, toplamlarıtargetolmalıdır. İkisi de daha kısa bir dizide aynı sorudur.ikonumundan sonraki değerlerin toplamıryapıp yapamayacağı yalnızcaiverdeğerlerine bağlıdır verhiçbir zamantargetdeğerini aşmaz. Dolayısıyla yaklaşık 200 × 10^4 farklı soru vardır ve her biri bir kez yanıtlanabilir.0'dan
target'a kadar her toplam için bir boolean kullan; başlangıçta yalnızca 0 toplamına ulaşılabilir olsun. Değerleri teker teker ekle:s-numzaten ulaşılabilir durumdaysastoplamına ulaşılabilir hâle gelir. Bir değerin iki kez kullanılmaması için toplamları büyükten küçüğe güncelle ve yanıtıtargetkonumundan oku.
Çözüm
Her değer için seçim evet ya da hayırdır; bu yüzden 200 değer 2^200 seçim verir. Ancak yalnızca target ≤ 10^4 değerine kadar olan toplamlar önemlidir. Şimdiye kadarki değerlerle hangi toplamların elde edilebileceğini kaydedin: her yeni değer bu kaydı kendi büyüklüğü kadar kaydırır ve arama, n × target boyutunda bir boolean tablosuna dönüşür.
Her değeri al veya atla
Doğru, ama en büyük testlerde bitmiyor
Sezgi
canMake(i, remaining), i konumundan itibaren değerlerin toplamının tam olarak remaining olup olamayacağını sorar. Uygun olduğunda nums[i] değerini alır; böylece geri kalanlar için remaining-nums[i] kalır. Bu işe yaramazsa o değeri atlar. Her seçim bir yol olduğundan, arama varsa bir seçim bulur.
Hiçbir seçim işe yaramadığında, hepsini dener. Her biri en fazla 300 olan 200 adet 3 katı ve 9998 hedefiyle hiçbir seçim işe yaramaz; ancak herhangi 33 değerin toplamı hedefin altında kalır: 10^37'den fazla yol.
Algoritma
canMake(i, remaining)yaz.remainingdeğerinin 0 olması, seçimin tamamlandığı anlamına gelir: true döndür. Hiç değer kalmadıysa ve hâlâ oluşturulması gereken bir şey varsa false döndür.nums[i] ≤ remainingise vecanMake(i+1, remaining-nums[i])true döndürüyorsa true döndür.- Aksi takdirde
canMake(i+1, remaining)döndür. canMake(0, target)döndür.
def isSubsetSum(nums, target):
n = len(nums)
# Can some of nums[i], nums[i+1], ... add up to exactly remaining?
def can_make(i, remaining):
if remaining == 0:
return True
if i == n:
return False
if nums[i] <= remaining and can_make(i + 1, remaining - nums[i]):
return True # take nums[i]
return can_make(i + 1, remaining) # skip it
return can_make(0, target)Erişilebilir toplamlar tablosunu doldur
Sezgi
Özyineleme yalnızca bir konuma ve 0 ile target arasındaki kalan toplama bağlıdır ve birçok yol aynı çifte ulaşır. Bunun yerine bir tablo doldurun. made[i][s], ilk i değerden yapılan bir seçimin toplamı tam olarak s olduğunda true değerini alır; boş seçim 0'ı oluşturur. num = nums[i-1] iken s toplamı, num kullanılmadan elde edilmişse (made[i-1][s]) ya da s ≥ num koşulunda num, s-num toplamını tamamlıyorsa (made[i-1][s-num]) elde edilir.
İlk örnekte, 8'den sonra elde edilen toplamlar 0 ve 8'dir. 3, 3 ve 11'i ekler; 11 yalnızca 14'ü ekler; 5, 5 ve 13'ü ekler ve 8 + 7, 15'e ulaşır. Sınır değerlerinde tablo 201 × 10001 hücre içerir; bu da yaklaşık 2 × 10^6 adım demektir.
Algoritma
madedeğişkenini, tümü false olan n+1 satır ve target+1 sütundan oluşacak şekilde ayır. Boş seçim içinmade[0][0]değerini true olarak işaretle.i. satır, i = 1 ile n arasında,num = nums[i-1]değerini ele alır.- 0'dan
targetdeğerine kadar herstoplamı içinmade[i][s]değerinimade[i-1][s]olarak ayarla. s ≥ numise vemade[i-1][s-num]true isemade[i][s]değerini true olarak ayarla.made[n][target]değerini döndür.
def isSubsetSum(nums, target):
n = len(nums)
# made[i][s]: some of the first i values add up to exactly s
made = [[False] * (target + 1) for _ in range(n + 1)]
made[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 on top of a sum of s-num
made[i][s] = made[i - 1][s] or (s >= num and made[i - 1][s - num])
return made[n][target]Üstten güncellenen bir toplama satırı
Sezgi
Her satır yalnızca kendisinden önceki satırı okur; bu yüzden tek bir made[s] dizisi onu tutabilir. Diziyi yukarı doğru üzerine yazarak güncellersen bir değer kendisini besler: nums = [5] ve hedef 10 iken, s = 5 true olur, ardından s = 10 bu yeni girdiyi okuyarak 5’i iki kez kullanır.
Bunun yerine target değerinden num değerine doğru ilerle. s-num konumundaki okuma, yürüyüşün henüz yeniden yazmadığı daha düşük bir hücreye denk gelir; dolayısıyla num değerinden önceki satırı görür. Bir toplam oluşturulmuşsa oluşturulmuş olarak kalır, bu yüzden made[target] true olur olmaz durabilirsin. Bellek kullanımı target + 1 boole değerine düşer.
Algoritma
- Yalnızca
made[0]değerinin true olduğu,target + 1booleandan oluşan tek bir diziyle başla. - Değerleri sırayla ele al. Her
numiçinsdeğerinitarget'tannum'a doğru azaltarak ilerle. made[s-num]değerinin bulunduğu her yerdemade[s]değerini işaretle.made[target]işaretlenir işaretlenmeztrueile dur.- Önce tüm değerler tükenirse yanıt
falseolur.
def isSubsetSum(nums, target):
# made[s]: some of the values seen so far add up to exactly s
made = [False] * (target + 1)
made[0] = True
for num in nums:
# Downward, so made[s - num] still ignores num
for s in range(target, num - 1, -1):
if made[s - num]:
made[s] = True
if made[target]:
return True
return False
Tuzaklar ve uç durumlar
- Toplamlar üzerinde artan yönde döngü, bir değeri iki kez kullanır:
[3]hedef 9 için true yanıtını verir. made[0] = truesatırını unutmak. Her toplam boş seçim üzerine kurulur, bu yüzden her yanıt false çıkar.- Önce en büyük değerleri seçmek. Hedef 10 iken
[6, 5, 5]dizisinde 6'yı almak geriye 4 bırakır ve bu toplamı hiçbir değer oluşturamaz; oysa 5 + 5 = 10. targetdeğerinden büyük bir değer,[10000]dizisinin hedef 1 olması örneğinde olduğu gibi, hiçbir şeyi değiştirmemelidir. Swift'tekinum...targetprogramı durdurur ve R'deki(num+1):(target+1)geriye doğru sayar; bu yüzden öncenum ≤ targetkoşulunu kontrol edin.- Lua ve R'de toplam
siçin giriş,s + 1dizininde bulunur.
Sıkça sorulan sorular4
Alt küme toplamı probleminin zaman karmaşıklığı nedir?
Tablo O(n × target) zaman alır; 200 değer ve 10^4 hedef için yaklaşık 2 × 10^6 adım gerekir ve tek bir satır belleği O(target) değerine düşürür. Maliyet, hedefin sayısal büyüklüğüne bağlıdır; bu nedenle yöntem sözde polinomdur ve 10^18 gibi bir hedef için işe yaramaz. Genel olarak, alt küme toplamı NP-tamdır.
Alt Küme Toplamı, Eşit Alt Kümelere Bölme ve 0/1 sırt çantası problemiyle nasıl ilişkilidir?
Eşit Alt Küme Toplamı, toplamın çift olduğu kontrol edildikten sonra target = total / 2 ile Alt Küme Toplamı problemidir. Alt Küme Toplamı, her değerin kendi ağırlığı olduğu ve çantanın tam olarak doldurulması gereken bir 0/1 sırt çantası problemidir; bu nedenle tabloda en iyi değerler yerine Boole değerleri tutulur.
Alt küme toplamı negatif sayılarla çalışır mı?
Fikir işe yarıyor, ancak yukarıdaki kod işe yaramıyor. Negatif sayılar olduğunda erişilebilir toplamlar, negatif sayıların toplamından pozitif sayıların toplamına kadar uzanır; bu nedenle her indeksi bu en düşük toplam kadar kaydır ve satırı aynı şekilde doldur. Kalan toplamdan büyük bir değer artık atlanamaz.
Hedefi hangi değerlerin oluşturduğunu nasıl bulursun?
Tüm tabloyu koru ve made[n][target] konumundan başla. Her seferinde bir satır yukarı çık: made[i-1][s] true ise nums[i-1] gerekli değildi; aksi hâlde onu kaydet ve s değerinden çıkar. Geçerli bir seçimle toplam 0 olduğunda durursun.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def isSubsetSum(nums, target):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argümanlar
nums = [8, 3, 11, 5, 7] target = 15
Beklenen Çıktı
true