Hedef toplamı veren kombinasyonlar

Problem

Birbirinden farklı pozitif tamsayılardan oluşan bir aday listesi ve bir hedef sayı veriliyor. Toplamı hedefe eşit olan tüm benzersiz kombinasyonları döndür. Her aday sınırsız kez kullanılabilir. İki kombinasyon, içerdikleri sayıların adetleri farklıysa farklıdır; sıra önemli değildir ([2, 2, 3] ile [3, 2, 2] aynıdır).

adaylar = [5, 3, 2, 4], hedef = 7
Çıktı: [2, 2, 3], [2, 5], [3, 4]

adaylar = [4, 6], hedef = 3   -> []
adaylar = [1],    hedef = 3   -> [[1, 1, 1]]

Netleştirme soruları

• Adaylar pozitif mi? (Evet. Sıfır ya da negatif olsaydı sonsuz kombinasyon olabilirdi.)
• Adaylar benzersiz mi? (Evet; tekrar olsaydı aynı kombinasyonlar tekrar üretilirdi.)
• Aynı aday birden fazla kullanılabilir mi? (Evet; her biri en fazla bir kez kullanılabilseydi Combination Sum II olurdu.)
• Çıktı sırası önemli mi? Kombinasyon içindeki sıra?
• Sadece kombinasyon sayısı mı isteniyor? (O zaman DP çok daha hızlıdır; takip sorusu.)

İpuçları

Yaklaşım

Saf arama: Her adımda herhangi bir adayı ekleyip hedefi aşana kadar devam etmek ve sonunda tekrar eden kombinasyonları (sıralayıp Set'e koyarak) temizlemek. Doğru ama aynı kombinasyonu permütasyon sayısı kadar üretir; çok israflı.

Başlangıç indeksli backtracking (seçilen çözüm): Kombinasyonları her zaman azalmayan indeks sırasıyla kurarız. backtrack(start, remaining), sadece i >= start adayları dener ve özyinelemeye i geçer (aynı aday tekrar seçilebilir, ama daha soldaki bir adaya geri dönülemez). Böylece her kombinasyon tam bir yoldan üretilir ve tekrar temizliğine gerek kalmaz.

Budama: Adaylar sıralıysa ve candidates[i] > remaining ise, bu ve sonraki tüm adaylar hedefi aşar; continue değil break doğrudur. Bu, arama ağacının büyük kısmını keser. Sıralama girdinin bir kopyası üzerinde yapılır; çağıranın dizisini değiştirmek bir yan etkidir.

Neden DP değil? Kombinasyonların listesi istendiği için çıktının kendisi üstel olabilir; DP sadece sayıyı ya da varlığı hızlıca bulur. Listeleme için backtracking doğal araçtır.

Java çözümü

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public final class CombinationSum {

    /** Adaylar pozitif ve birbirinden farklı; her aday sınırsız kullanılabilir. */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int[] sorted = candidates.clone();
        Arrays.sort(sorted);                               // budama için: büyük adaylar erken kesilir
        List<List<Integer>> result = new ArrayList<>();
        backtrack(sorted, 0, target, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] sorted, int start, int remaining, List<Integer> current, List<List<Integer>> result) {
        if (remaining == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
        for (int i = start; i < sorted.length; i++) {
            if (sorted[i] > remaining) break;              // sıralı: sonrakiler de sığmaz
            current.add(sorted[i]);
            backtrack(sorted, i, remaining - sorted[i], current, result);   // i (i+1 değil): aynı aday tekrar seçilebilir
            current.remove(current.size() - 1);
        }
    }
}

Subsets ile tek yapısal fark özyinelemede i + 1 yerine i geçilmesidir; bu tek karakter "her eleman bir kez" ile "her eleman sınırsız" arasındaki farktır. Mülakatta bu satırı yorumla açıklamak, kodun bilinçli yazıldığını gösterir.

Karmaşıklık

Backtracking karmaşıklığı kesin olarak ifade etmek zordur; standart üst sınır:

• Zaman: O(N^(T/M + 1)); N aday sayısı, T hedef, M en küçük aday. Ağacın derinliği en fazla T/M, her düğümde en fazla N dal. Budama pratikte bunu çok azaltır. Sonuca kopyalama, kombinasyon başına O(T/M) ek iş getirir.
• Bellek: Çıktı hariç O(T/M) özyineleme derinliği ve current listesi.

Mülakatta bu sınırı türetebilmek, kesin bir sayı vermekten daha değerlidir.

Kenar durumlar ve testler

Testler main içinde çalıştırıldı:

• [5, 3, 2, 4], 7: [[2, 2, 3], [2, 5], [3, 4]] (sıralı adaylar sayesinde deterministik sıra).
• Hiçbir kombinasyon yok ([4, 6], 3): boş liste.
• Tek aday tekrarı ([1], 3): [[1, 1, 1]].
• Girdi dizisi değişmemiş ([3, 1, 2] aynı kaldı).
• 1.000 rastgele girdi (1-5 benzersiz aday 2-13 arası, hedef 1-30): sonuç sayısı, sınırsız sırt çantası DP'siyle hesaplanan kombinasyon sayısına eşit; her kombinasyonun toplamı hedefe eşit; sıralanmış hiçbir kombinasyon iki kez yok.

Bu son test önemli bir teknik gösterir: listeyi doğrudan doğrulamak zor olduğunda, bağımsız bir yolla hesaplanan sayı ve her elemanın geçerliliği birlikte kontrol edilir.

Mülakatçı için

Gözlemlenecekler: tekrarları önleme yöntemi (başlangıç indeksi mi, sonradan Set ile temizlik mi), i ile i + 1 farkının bilinçli olması, budamanın varlığı ve break/continue farkı, sonuca kopya eklenmesi. Karmaşıklık analizinde adayın ağaç derinliği ve dallanma faktörüyle akıl yürütmesini bekle.

İpucu zamanlaması: Aday tekrar eden kombinasyonlar üretirse ([2, 3, 2] gibi) hatayı söyleme; küçük bir örnek çıktısını yazmasını iste. 3-4 dakikada çözüm gelmezse birinci ipucunu ver. Budamayı kendiliğinden eklemeyen adaya "bu döngüde gereksiz iş var mı?" diye sor.

Takip sorusu 1: Her aday en fazla bir kez kullanılabilsin ve adaylar tekrar edebilsin. Beklenen: özyinelemede i + 1, sıralanmış dizide i > start && c[i] == c[i-1] ise atla (LeetCode 40).

Takip sorusu 2: Sadece kombinasyon sayısını döndür; hedef 10^4. Beklenen: ways[s] += ways[s - c], dış döngü adaylar; O(N · T). Dış döngü toplam olursa sıralı dizileri (permütasyonları) sayar (Combination Sum IV, LeetCode 377).

Takip sorusu 3: Bir e-ticaret sitesinde "sepetinizi tam 500 TL'ye tamamlayacak ürün kombinasyonları" özelliği. Ne değişir? Beklenen: ürün sayısı büyük, çıktı üstel; ilk k sonuçla sınırlamak, fiyatları kuruş olarak long/int tutmak (ondalık hata), yaklaşık eşleşmeye izin vermek, sonuçları popülerliğe göre sıralamak; gerektiğinde DP ile önce varlık kontrolü.

Benzer problemler

• Combination Sum II (LeetCode 40)
• Combination Sum III (LeetCode 216)
• Combination Sum IV (LeetCode 377)
• Subsets (LeetCode 78)
• Coin Change II (LeetCode 518)