Pozitif ve Negatif İşaretlerle Hedef Toplam
Hedef toplam atama problemini alt küme toplamı farkı üzerine kurulu bir sırt çantasına dönüştürün ve O(n × sum) sürede çözün.
Pozitif ve Negatif İşaretlerle Hedef Toplam, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 4. 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.
Hedef Toplam Problemi
Bir tamsayı dizisi olan nums ve bir tamsayı olan target verildiğinde, sonuçta oluşan ifadenin target değerine eşit olması için her sayıya bir + veya - işareti atayın. Bunu yapmanın farklı yollarının sayısını döndürün. Örneğin, nums=[1,1,1,1,1] ve target=3 için 5 yol vardır (farklı konumlarda 4 elemanı pozitif, 1 elemanı negatif seçerek).
Kaba Kuvvet: DFS Numaralandırması
Bir DFS yaklaşımı her sayıya + veya - işareti atar ve özyinelemeli olarak ilerler; target değerine ulaşan yaprak düğümlerin sayısını döndürür. Bu yaklaşım doğrudur; ancak O(2^n) zaman karmaşıklığına sahiptir — yani üsteldir. n=20 için bir milyondan fazla özyinelemeli çağrı yapılır. DFS yaklaşımından önce bahsetmek, ardından hızla DP iyileştirmesine geçmek mülakatlarda değerlidir.
def findTargetSumWays_dfs(nums, target):
count = [0]
def dfs(i, current_sum):
if i == len(nums):
if current_sum == target:
count[0] += 1
return
dfs(i+1, current_sum + nums[i])
dfs(i+1, current_sum - nums[i])
dfs(0, 0)
return count[0]
print(findTargetSumWays_dfs([1,1,1,1,1], 3)) # 5Önbelleklemeli DFS
DFS'ye önbellekleme ekleyin: durum (index, current_sum) şeklindedir. Mevcut toplam -total ile +total arasında değişebildiğinden O(n × toplam) benzersiz durum vardır. Önbellekleme ile DFS, O(n × toplam) zaman ve alan kullanarak çalışır. Bu yöntem çalışır ve mülakatlarda geçerlidir; ancak dönüşüm temelli DP daha zarif ve alan açısından daha verimlidir.
from functools import lru_cache
def findTargetSumWays_memo(nums, target):
total = sum(nums)
@lru_cache(maxsize=None)
def dp(i, remaining):
if i == len(nums):
return 1 if remaining == 0 else 0
return dp(i+1, remaining - nums[i]) + dp(i+1, remaining + nums[i])
return dp(0, target)
print(findTargetSumWays_memo([1,1,1,1,1], 3)) # 5Matematiksel Dönüşüm
P, + atanan sayıların kümesi; N ise - atanan sayıların kümesi olsun. Buna göre: sum(P) - sum(N) = target ve sum(P) + sum(N) = total. Toplayınca: 2 × sum(P) = target + total, dolayısıyla sum(P) = (target + total) / 2 olur. Problem şu soruya indirgenir: nums dizisinde toplamı (target + total) / 2 olan alt kümelerin sayısı kaçtır? Bu, 0/1 sırt çantasının tam olarak alt kümeleri sayma çeşididir.
# sum(P) - sum(N) = target
# sum(P) + sum(N) = total
# => 2*sum(P) = target + total
# => sum(P) = (target + total) / 2
# Count subsets with sum = new_target = (target + total) // 2
print('Reduction: count subsets summing to (target + total) // 2')DP'den Önce Geçerlilik Kontrolleri
DP'yi çalıştırmadan önce şunları kontrol edin: (1) target + total çift olmalıdır (aksi hâlde sum(P) bir tamsayı olmaz ve çözüm mümkün değildir); (2) abs(target) > total olması, tüm işaretler aynı yönde olsa bile hedefe ulaşılamayacağı anlamına gelir. Bu kontrollerden biri başarısız olursa hemen 0 döndürün. Böylece DP döngüsü içinde özel durumlar ele almadan sınır durumlarını temiz biçimde yönetebilirsiniz.
def findTargetSumWays(nums, target):
total = sum(nums)
if (target + total) % 2 != 0:
return 0 # sum(P) would be non-integer
if abs(target) > total:
return 0 # impossible to reach
new_target = (target + total) // 2
# Count subsets summing to new_target
dp = [0] * (new_target + 1)
dp[0] = 1
for num in nums:
for c in range(new_target, num - 1, -1):
dp[c] += dp[c - num]
return dp[new_target]
print(findTargetSumWays([1,1,1,1,1], 3)) # 5Küçük Bir Örneği Adım Adım İzleme
nums=[1,1,1,1,1] ve target=3 için: toplam=5, yeni hedef=(3+5)//2=4. [1,1,1,1,1] içinden toplamı 4 olan alt kümeleri sayarız. Bu, C(5,4)=5 değeridir (4 tane 1'i pozitif seçeriz, 5. sayı negatiftir: 1+1+1+1-1=3). DP doğru biçimde 5 döndürür. Bu dönüşüm, işaret atama problemini zarif bir şekilde standart bir alt küme sayma problemine dönüştürür.
nums İçindeki Sıfırları Ele Alma
nums sıfırlar içeriyorsa, sıfıra + veya - atamak toplamı değiştirmez. Her sıfır, geçerli atamaların sayısını iki katına çıkarır. DP bunu doğal olarak ele alır: num=0 işlenirken iç döngü range(new_target, -1, -1) yeni hedeften 0'a kadar ilerler ve dp[c] += dp[c - 0] = dp[c] tüm ulaşılabilir toplamları iki katına çıkarır. range(new_target, num-1, -1) kullanırsanız özel bir işlem gerekmez; bu ifade num=0 olduğunda new_target değerinden 0'a kadar ilerler.
# With zeros: each zero doubles the count
print(findTargetSumWays([0, 0, 1], 1)) # 4
# Assignments: +0+0+1, +0-0+1, -0+0+1, -0-0+1 = all give sum 1Karmaşıklık Karşılaştırması
Kaba kuvvet DFS'si O(2^n) karmaşıklığına sahiptir. Önbelleklemeli DFS, zaman ve alan açısından O(n × toplam) kullanır. Dönüşüm temelli 1B DP ise new_target ≤ total olmak üzere zaman açısından O(n × new_target), alan açısından O(new_target) kullanır. 1B DP, dönüşüm sayesinde dizin boyutunu ortadan kaldırdığı için önbelleklemeden önemli ölçüde daha az alan kullanır.
Diğer Sırt Çantası Problemleriyle Bağlantı
Hedef Toplam, birden fazla sırt çantası kavramını bir araya getirir: bir atama problemi olarak başlar, alt küme toplamına (Eşit Toplamlı Alt Kümelere Bölme gibi) dönüşür ve sayma işlemiyle (Madeni Para Değişimi II gibi) aynı 0/1 sırt çantası geriye doğru dolaşma şablonunu kullanır. Bu bağlantılara hâkim olmak, mülakatlarda yeni problemleri bilinen örüntülerle yapısal benzerliklerine göre hızla sınıflandırmanızı sağlar.
Sınır Durumları ve Mülakat Notları
Temel durumlar: (1) target = total: yalnızca bir yol vardır (tümü pozitif); (2) target = -total: yalnızca bir yol vardır (tümü negatif); (3) tüm elemanlar sıfırken target = 0: sonuç 2^n olur; (4) n küçük, total çok büyükse — 1B DP dizisinin boyutu total/2 ile sınırlıdır. Mülakatlarda kodlamaya başlamadan önce dönüşüm adımını sözlü olarak açıklayın; güçlü adayları diğerlerinden ayıran, fark edilmesi kolay olmayan içgörü budur.
Dönüşüm Olmadan 2B DP Alternatifi
Dönüşüm olmadan, dp[i][s] değerini ilk i sayıya işaret atayarak s toplamına ulaşmanın yol sayısı olarak tanımlayın. Toplam negatif olabileceğinden, toplam kadar öteleyin: dp[i][s + total] kullanın. Bunun için (n+1) × (2*total+1) boyutunda 2B bir tablo gerekir. Doğru olsa da bu yöntem daha fazla alan kullanır ve dönüşümden sonraki 1B sırt çantasına kıyasla mülakat baskısı altında hızlı kodlanması daha zordur.
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: Hedef Toplam, işaret atama problemini toplamı (target + total) / 2 olan alt kümeleri sayma problemine dönüştürür, 1B 0/1 sırt çantasının geriye doğru dolaşması alt kümeleri O(n × new_target) zamanında ve O(new_target) alanında sayar ve erken geçerlilik kontrolleri (çift olmayan toplam, |target| > total) gereksiz DP çalıştırılmasını önler. Sırada, Dijkstra algoritması ve öncelik kuyruğuyla en kısa yol konusuna geçiyoruz.
Sıkça Sorulan Sorular
“Pozitif ve Negatif İşaretlerle Hedef Toplam” dersi ücretsiz mi?
Evet — “Pozitif ve Negatif İşaretlerle Hedef Toplam” 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.
“Pozitif ve Negatif İşaretlerle Hedef Toplam” dersinde ne öğreneceğim?
Hedef toplam atama problemini alt küme toplamı farkı üzerine kurulu bir sırt çantasına dönüştürün ve O(n × sum) sürede çözün. 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 4. dersidir.
“Pozitif ve Negatif İşaretlerle Hedef Toplam” 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