Combination Sum
Farklı pozitif tam sayılardan oluşan bir candidates listesi ve pozitif bir target tam sayısı veriliyor. İstediğin adayı istediğin kadar kullanarak toplamı tam olarak target olan tüm kombinasyonları bul. [2, 3, 3] ve [3, 2, 3] aynı kombinasyondur.
Her kombinasyonu artan sırada, kombinasyonları ise sözlük sırasına göre döndür: İki kombinasyonun farklı olduğu ilk konumda, daha küçük değere sahip olan önce gelir.
Fonksiyon
- candidatesinteger-array
- kullanabileceğin farklı değerler; istediğin sırada ve her birini istediğin kadar kullanabilirsin
- targetinteger
- her kombinasyonun toplamı tam olarak şu değere ulaşmalıdır
- Döndürürinteger-2d-array
- hedefe ulaşan her kombinasyon, her biri artan sırada olacak şekilde, sözlük sırasına göre listelenir
Kısıtlar
1 ≤ candidates.length ≤ 502 ≤ candidates[i] ≤ 5002 ≤ target ≤ 500-
candidatesiçindeki tüm değerler birbirinden farklıdır ve belirli bir sırada değildir. - En az bir kombinasyon
targetdeğerine ulaşır ve en fazla 150 kombinasyon ulaşır.
Örnekler
- Girdi
- candidates = [6, 2, 3]target = 8
- Çıktı
- [[2, 2, 2, 2], [2, 3, 3], [2, 6]]
- Açıklama
- Dört tane 2, 2 + 3 + 3 ve 2 + 6 toplamlarının hepsi 8 eder; ikinci değerlerine göre sıralanmıştır. 2 olmadan yalnızca 3'ler ve 6'lar kalır ve bunların toplamları 3'ün katıdır; 8 ise değildir.
- Girdi
- candidates = [5, 3, 4]target = 11
- Çıktı
- [[3, 3, 5], [3, 4, 4]]
- Açıklama
- 3 + 3 + 5 ve 3 + 4 + 4 toplamlarının ikisi de 11 eder ve
[3, 3, 5]önce gelir çünkü ikinci değeri olan 3, 4'ten küçüktür. Yalnızca 4'lerin ve 5'lerin hiçbir kombinasyonu 11 etmez.
- Girdi
- candidates = [4, 9]target = 9
- Çıktı
- [[9]]
- Açıklama
- Tek başına 9 tek cevaptır: 4'ün katları 4, 8 ve 12'dir; 4 + 9 ise zaten 13 eder.
Ek soru
Artık her aday en fazla bir kez kullanılabilir ve candidates tekrarlanan değerler içerebilir. Hiçbir kombinasyonun iki kez görünmemesi için aramayı nasıl değiştirirsin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
[2, 3, 3]ve[3, 2, 3]aynı kombinasyondur. Bir kombinasyonu yalnızca değerleri artan sırada olacak şekilde oluşturursan, her biri kaç farklı şekilde oluşturulabilir?Adayları sırala ve her seferinde bir değer ekleyerek bir kombinasyon oluştur.
nums[i]değerini ekledikten sonra, sonraki değer yinenums[i]veya daha sonraki herhangi bir değer olabilir; daha önceki bir değer olamaz.backtrack(start, remaining)yaz.remaining0 olduğunda geçerli değerlerin bir kopyasını kaydet. Aksi takdirdestartnoktasından başlayarak döngüye gir: bir değer ekle, aynı indeks ve daha küçük kalan değerle özyinelemeli çağrı yap, ardından değeri kaldır.remainingdeğerinden büyük olan ilk değerde döngüden çık.
Çözüm
Buradaki tuzak, aynı kombinasyonu iki kez oluşturmaktır: 2, 3, 3 ve 3, 2, 3 aynı yanıttır. Her kombinasyonu artan sırada oluştur, böylece tam olarak tek bir yolu olur ve adayları sırala; böylece sonraki değer kalan miktardan büyük olduğunda bir dal hemen durur.
Her adayın her sayısını dene
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Bir kombinasyon, her adaydan kaç kopya kullandığıyla tamamen tanımlanır: [2, 3, 3], bir tane 2, iki tane 3 ve hiç 6 olmadığı anlamına gelir. Sıralanmış her aday için target / c değerinden 0'a kadar tüm sayıları deneyin ve toplamı tam olarak target olan seçimleri tutun. Her kombinasyonun tek bir sayı listesi vardır, dolayısıyla hiçbiri iki kez bulunmaz. Önce daha büyük sayıları denemek sözlük sırası oluşturur: iki yanıtın ilk farklılaştığı yerde, bir değerden daha fazla kopyaya sahip olan yanıt o değeri tutarken diğeri daha büyük bir değeri tutar.
[2, 3, 6] ve 8 hedefi için 3 yanıtı bulmaya yönelik 5 × 3 × 2 = 30 yaprak vardır. target / 2 değerinden büyük her aday, yaprak sayısını ikiye katlar; dolayısıyla 40 böyle aday, 2^40, yani yaklaşık 10^12 yaprak demektir.
Algoritma
- Adayları sırala ve her değer için bir sayaç tut.
choose(i, total)içinde,target / nums[i]değerinden 0'a kadar herksayısını dene vechoose(i + 1, total + k × nums[i])çağrısını yap.- Her değer için bir sayaç belirlendiğinde,
totaldeğeritargetdeğerine eşitse kombinasyonu tut ve sayaçlardan oluştur. choose(0, 0)çağrısını yap.
def combinationSum(candidates, target):
nums = sorted(candidates)
counts = [0] * len(nums)
result = []
def choose(i, total):
if i == len(nums):
if total == target:
combo = []
for value, k in zip(nums, counts):
combo.extend([value] * k)
result.append(combo)
return
# Most copies first, so the combinations come out in lexicographic order.
for k in range(target // nums[i], -1, -1):
counts[i] = k
choose(i + 1, total + k * nums[i])
counts[i] = 0
choose(0, 0)
return resultArtan sırayla geri izleme yap ve budama uygula
Sezgi
nums[i] değerini yerleştirdikten sonra, sonraki değer yine nums[i] veya daha sonraki herhangi bir değer olabilir; daha önceki bir değer olamaz. Bir kombinasyonun tam olarak bir artan sıralaması olduğundan, tam olarak bir yolu vardır ve [3, 2, 3] asla oluşturulmaz.
Sıralanmış [2, 3, 6] ve hedef 8 için 2, 2, 2, 2; 2, 3, 3 ve 2, 6 yolları 8'e ulaşır. 2, 2, 3 yolu geriye 1 bırakır ve 6'ya bakmadan durur; 3, 3 ise geriye 2 bırakır ve bu değere uyan hiçbir değer yoktur. Bu, sayma yöntemindeki 30 yaprak düğüme karşılık 12 çağrıdır.
Her seviyede döngü önce daha küçük değerleri denediğinden, yanıtlar sözlük sırasıyla gelir. Değerler pozitif olduğundan ve her ikisi de aynı toplama ulaştığından, hiçbir yanıt diğerinin öneki değildir.
Algoritma
- Adayları sırala.
backtrack(start, remaining)içinde,remaining0 olduğunda paylaşılanpathdeğişkeninin bir kopyasını kaydet.- Aksi takdirde
iiçinstartnoktasından başlayarak döngüye gir.nums[i] > remainingise döngüden çık: sonraki tüm değerler daha büyüktür. nums[i]değerini ekle,backtrack(i, remaining - nums[i])çağrısını yap, ardından bu değeri kaldır.backtrack(0, target)çağrısını yap ve kaydedilen kombinasyonları döndür.
def combinationSum(candidates, target):
nums = sorted(candidates)
result = []
path = []
def backtrack(start, remaining):
if remaining == 0:
result.append(path[:])
return
for i in range(start, len(nums)):
if nums[i] > remaining:
break # sorted, so every later value is too big as well
path.append(nums[i])
backtrack(i, remaining - nums[i]) # i, not i + 1: nums[i] may repeat
path.pop()
backtrack(0, target)
return result
Tuzaklar ve uç durumlar
- Geçerli her düzeyde mevcut indisten başlamak yerine her adayı dolaşmak. Böylece
[2, 3, 3],[3, 2, 3]ve[3, 3, 2]üç ayrı yanıt olarak ortaya çıkar. iyerinei + 1ile özyinelemeli çağrı yapmak. Böylece her değer yalnızca bir kez görünebilir ve[2, 2, 2, 2]eksik kalır.pathöğesinin bir kopyası yerine doğrudan kendisini kaydetmek. Böylece kaydedilen tüm yanıtlar, geri izleme işleminin sonunda boşalttığı aynı liste olur.- Sıralamadığınız adaylarda
breakkullanmak. Geride 2 kaldığında[6, 2, 3]için döngü 6'da durur ve 2'yi hiç denemez.
Sıkça sorulan sorular3
Combination Sum'ın zaman karmaşıklığı nedir?
Geri izleme araması üstel zamandadır. n aday, t hedefi ve en küçük aday m verildiğinde, bir kombinasyon en fazla t/m değer içerir ve her biri için en fazla n seçenek bulunur: O(n^(t/m)). Ek alan, yol ve çağrı yığını için O(t/m) kadardır; çıktıya ayrılan alan buna eklenir.
Combination Sum'da neden i + 1 yerine i ile özyinelemeli çağrı yapıyorsunuz?
i ile özyineleme yapmak, sonraki değerin yine aynı aday olmasını sağlar; bir değerin birden fazla kez kullanılabilmesinin nedeni budur. i + 1 ile özyineleme yapmak ise onu geçer, böylece her aday en fazla bir kez kullanılabilir.
Combination Sum dinamik programlamayla çözülebilir mi?
Evet. 0'dan target değerine kadar her toplam için, o toplama ulaşan kombinasyonları tut ve her seferinde bir aday ekleyerek her listenin artan sırada kalmasını sağla. Çıkmaza iki kez girmez, ancak her toplam için tüm kısmi kombinasyonları saklar; bu da çok daha fazla bellek kullanır. Çıktının kendisi üstel büyüyebileceğinden, genellikle geri izleme tercih edilir.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def combinationSum(candidates, target):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argümanlar
candidates = [6, 2, 3] target = 8
Beklenen Çıktı
[[2, 2, 2, 2], [2, 3, 3], [2, 6]]