Subset Sum Problemi (Alt Küme Toplamı)

1function findSubsetSum(arr: number[], targetSum: number): number[][] {
2  const result: number[][] = [];
3  const currentSubset: number[] = [];
4  const sortedArr = [...arr].sort((a, b) => a - b);
5  
6  function backtrack(start: number, currentSum: number) {
7    if (currentSum === targetSum) {
8      result.push([...currentSubset]);
9      return;
10    }
11    
12    if (currentSum > targetSum) {
13      return;
14    }
15    
16    for (let i = start; i < sortedArr.length; i++) {
17      if (i > start && sortedArr[i] === sortedArr[i - 1]) {
18        continue;
19      }
20      
21      currentSubset.push(sortedArr[i]);
22      backtrack(i + 1, currentSum + sortedArr[i]);
23      currentSubset.pop();
24    }
25  }
26  
27  backtrack(0, 0);
28  return result;
29}