Combination Sum

Bir kombinasyon, her adaydan kaç kopya kullandığıyla tamamen tanımlanır. [6, 2, 3] ve hedef 8 için [2, 3, 3] yanıtı bir tane 2, iki tane 3 ve hiç 6 içermez. Dolayısıyla her yanıtı bulmanın bir yolu, her aday için olası tüm adetleri denemek ve toplamı tam olarak target olan seçimleri tutmaktır. Bir aday c, en fazla target / c kez kullanılabilir; bu nedenle adedi 0'dan bu sınıra kadar değişir.

Adayları sıraladıktan sonra, her aday için bir seviye içeren bir karar ağacı düşünün. i. seviyede, i. değerden kaç kopya alacağınıza karar verirsiniz ve en alttaki her yaprak, eksiksiz bir adet seçimini temsil eder. Her çoklu kümenin tam olarak bir adet listesi olduğundan, hiçbir kombinasyon iki kez bulunmaz. En büyük adedi önce denemek, istenen sıralamayı da sağlar: iki yanıt bir değerin adedinde ilk kez farklılaştığında, daha fazla kopya içeren yanıt, diğer yanıt daha büyük bir değer içerirken o küçük değeri hâlâ içerir; bu nedenle önce gelir.

Sorun ağacın boyutudur. Yaprak sayısı, tüm adaylar için target / c + 1 değerlerinin çarpımıdır: sıralanmış [2, 3, 6] ve hedef 8 için 3 yanıt karşılığında 5 × 3 × 2 = 30 yaprak vardır. target / 2 değerinden büyük her aday, en fazla bir kez kullanılabilmesine rağmen yaprak sayısını ikiye katlar; dolayısıyla yalnızca bu türden 40 aday bile 2^40, yani yaklaşık 10^12 yaprak demektir. Büyük testler bu şekilde hazırlanmıştır ve bu yaklaşım onları tamamlayamaz.

Her kombinasyonu, onu yazacağın sırayla, her seferinde bir değer ekleyerek oluştur: artan sırada. Başlangıç indeksi bu sırayı zorunlu kılar. nums[i] değerini ekledikten sonra sıradaki değer yine nums[i] olabilir, çünkü bir aday tekrarlanabilir; sonraki herhangi bir değer de olabilir, ancak daha önceki bir değer olamaz. Bu yüzden i indeksini ekleyen çağrı yalnızca i indeksinden itibaren döngüye girer. Her kombinasyonun artan sırada tam olarak bir yazılışı vardır; dolayısıyla ağaçta tam olarak bir yolu bulunur ve [3, 2, 3] gibi bir tekrar asla oluşturulmaz.

Sıralanmış [2, 3, 6] ve hedef 8 için tüm ağaç şöyledir. Kökün kalan değeri 8'dir ve 2, 3 ve 6'yı dener. 2'nin altında 6 kalır. 2, 2'nin altında 4 kalır ve 2, 2, 2'den sonra 2 kalır; bir 2 daha eklendiğinde yanıt [2, 2, 2, 2] olur; 2, 2, 3'ten sonra 1 kalır ve bu yol sonuç vermez. 2, 3'ün altında 3 kalır ve yalnızca 3 ile 6 denenebilir; 3, [2, 3, 3] sonucunu verir. 2, 6'nın altında hiçbir şey kalmaz: [2, 6]. 3'ün altında yalnızca 3 ile 6 denenebilir ve 3, 3'ten sonra 2 kalır; bu da hiçbirini tamamlamaz. 6'nın altında 2 kalır ve yalnızca 6 denenebilir. Toplamda 12 çağrı; ilk yaklaşımın 30 yaprak düğümüne kıyasla.

Sıralama, çıkmaz bir yolu erken durmaya dönüştürür. nums[i] kalan değerden büyük olduğunda, sonraki tüm değerler de büyük olur; bu yüzden geri kalanını denemek yerine break ile döngüden çıkarsın. Yukarıdaki ağaçta, 1 kalan 2, 2, 3 düğümü 3'e bakar, sığmadığını görür ve 6'ya hiç bakmaz. Arama yalnızca toplamı hâlâ target değerinden küçük veya ona eşit olan önekleri ziyaret eder; bu yüzden ilk yaklaşımı başarısız kılan büyük testler burada birkaç bin çağrı alır.

Çıktı sırası da aynı yürüyüşten gelir. Her düzeyde döngü önce daha küçük değerleri dener ve her kombinasyon artan sırada yazılır. İki yanıt ilk kez yollarının ayrıldığı düzeyde farklılaşır ve orada daha küçük değeri içeren yol önce araştırıldığı için yanıtlar sözlük sırasıyla gelir. Değerler pozitif olduğundan ve her iki kombinasyon da aynı toplama ulaştığından, bir kombinasyon başka bir kombinasyonun öneki olamaz.