Algoritmalar İnteraktif Öğrenme Platformu

Subset Sum Problemi (Alt Küme Toplamı)

Subset Sum (Alt Küme Toplamı) problemi, bir sayı dizisinden, toplamı belirli bir hedef değere eşit olan bir alt küme bulunup bulunamayacağını belirleyen bir problemdir. Bu, NP-Complete bir problemdir ve geri izleme (backtracking) algoritması, dinamik programlama (dynamic programming) veya brute force yaklaşımları ile çözülebilir.

İnteraktif Demo

Subset Sum problemini test etmek için bir sayı dizisi ve hedef toplamı girin. Algoritma, dizideki sayılardan oluşan ve toplamı hedef değere eşit olan tüm olası alt kümeleri bulacaktır.

Sayı Dizisi (virgülle ayrılmış)

Hedef Toplam

Algoritma:

Algoritma Bilgileri:

Geri İzleme: Tüm olası alt kümeleri bulur, üstel karmaşıklık.
Dinamik Programlama: Daha verimli, ancak benzer alt kümeler oluşturabilir.
Büyük diziler için hesaplama zaman alabilir.

Sonuçlar

Bulunan Alt Küme Sayısı:

Çözüm bulunamadı

Bu dizi ve hedef toplam için çözüm bulunamadı.

Kod Örnekleri

Subset Sum problemi için geri izleme algoritmasının farklı programlama dillerindeki implementasyonları.

Subset Sum Problemi - TypeScript

1function findSubsetSum(arr: number[], targetSum: number): number[][] {
2  // Bulunan alt kümeleri saklayacak dizi
3  const result: number[][] = [];
4  // Mevcut alt kümeyi oluşturmak için kullanılan dizi
5  const currentSubset: number[] = [];
6  
7  // Diziyi sırala (opsiyonel, ama budama için yardımcı olabilir)
8  const sortedArr = [...arr].sort((a, b) => a - b);
9  
10  // Geri izleme fonksiyonu
11  function backtrack(start: number, currentSum: number) {
12    // Hedef toplam bulundu, çözümü kaydet
13    if (currentSum === targetSum) {
14      result.push([...currentSubset]);
15      return;
16    }
17    
18    // Toplam hedefi aştı, bu dalı buda
19    if (currentSum > targetSum) {
20      return;
21    }
22    
23    // Tüm olası elemanları dene
24    for (let i = start; i < sortedArr.length; i++) {
25      // Aynı değere sahip ardışık elemanları atla (tekrarları önle)
26      if (i > start && sortedArr[i] === sortedArr[i - 1]) {
27        continue;
28      }
29      
30      // Elemanı alt kümeye ekle
31      currentSubset.push(sortedArr[i]);
32      
33      // Sonraki eleman için rekürsif çağrı
34      backtrack(i + 1, currentSum + sortedArr[i]);
35      
36      // Geri al (backtrack)
37      currentSubset.pop();
38    }
39  }
40  
41  // 0. indeksten ve 0 toplamdan başlayarak geri izleme algortimasını başlat
42  backtrack(0, 0);
43  
44  return result;
45}

Algoritma Nasıl Çalışır?

Subset Sum problemi, bir sayı dizisinden, toplamı belirli bir hedef değere eşit olan bir alt küme bulunup bulunamayacağını belirleyen bir problemdir. Bu problem için iki temel yaklaşım vardır: geri izleme (backtracking) ve dinamik programlama (dynamic programming).

Geri İzleme (Backtracking) Yaklaşımı

Geri izleme yaklaşımı, her sayı için iki seçenek olduğunu varsayar: sayı ya alt kümeye dahil edilir ya da edilmez. Bu, tüm olası alt kümeleri araştırmak için sistematik bir yol sağlar.

Deneme: Bir sayıyı alt kümeye ekle ve alt toplamı güncelle.
Kontrol: Eğer mevcut toplam hedef değere eşitse, çözümü kaydet.
Budama (Pruning): Eğer mevcut toplam hedef değeri aşıyorsa, bu dal daha fazla araştırılmaz.
Rekürsif Arama: Kalan sayılarla alt problemleri çöz.
Geri İzleme: Mevcut sayıyı alt kümeden çıkar ve başka bir dalı dene.

Dinamik Programlama (Dynamic Programming) Yaklaşımı

Dinamik programlama yaklaşımı, alt problemlerin sonuçlarını saklayarak ve tekrar kullanarak verimliliği artırır. Bu yöntemde, bir boolean tablosu kullanılır:

dp[i][j] = true anlamı: i. indekse kadar olan sayıları kullanarak j toplamını oluşturmak mümkün.
dp[i][j] = false anlamı: i. indekse kadar olan sayıları kullanarak j toplamını oluşturmak imkansız.

1D versiyonu için (uzay optimizasyonu ile):

dp[j] = true anlamı: j toplamını oluşturmak mümkün.
dp[j] = false anlamı: j toplamını oluşturmak imkansız.

İki Yaklaşımın Karşılaştırması

Geri İzleme:

Avantajları: Tüm olası çözümleri bulabilir, uzay verimliliği daha yüksek.
Dezavantajları: Üstel zaman karmaşıklığı, büyük diziler için çok yavaş olabilir.

Dinamik Programlama:

Avantajları: Daha iyi zaman verimliliği, büyük diziler için daha pratik.
Dezavantajları: Daha fazla bellek kullanımı, genellikle sadece çözümün var/yok bilgisini verir (tüm alt kümeleri vermez).

Optimizasyon Teknikleri

Subset Sum probleminin çözümünü hızlandırmak için kullanılabilecek bazı teknikler:

Sıralama: Diziyi sıralamak, erken budama fırsatları yaratabilir, özellikle büyük elemanlar daha erken reddedilebilir.
Tekrarları Eleme: Tekrar eden elemanları tek seferde işlemek (tekrar eden sayılar için aynı alt problemleri çözmemek).
Meet in the Middle: Diziyi iki parçaya bölerek, her biri için olası tüm toplamları hesaplamak ve ardından birleştirmek. Bu, 2^(n/2) karmaşıklığına düşürebilir.
Kesme İpuçları: Eğer toplam hedefi aşarsa hemen buda, eğer kalan elemanların toplamı hedef değeri tamamlamaya yetmiyorsa buda.

Algoritmik Varyasyonlar

Subset Sum probleminin birkaç varyasyonu vardır:

Karar Versiyonu: Sadece böyle bir alt kümenin var olup olmadığını belirler (evet/hayır).
Optimizasyon Versiyonu: Hedef değeri aşmadan ona en yakın toplamı bulan alt kümeyi belirler.
Sayma Versiyonu: Hedef toplamı oluşturan alt kümelerin sayısını belirler.
Tüm Çözümler Versiyonu: Hedef toplamı oluşturan tüm alt kümeleri bulur (bizim uyguladığımız).

Karmaşıklık Özeti

Geri İzleme Yaklaşımı:
- Zaman Karmaşıklığı: O(2^n)
- Uzay Karmaşıklığı: O(n) - rekürsif çağrı yığını için
Dinamik Programlama Yaklaşımı:
- Zaman Karmaşıklığı: O(n * targetSum)
- Uzay Karmaşıklığı: O(targetSum) - 1D DP tablosu için