從正負數集合中找出所有可能的子集總和等於0？

你必須擁有一組正數和負數的數組，打印所有的子集和等於0。從正負數集合中找出所有可能的子集總和等於0？

我能想到的辦法，我可以使凸輪陣列givcen所有powersets和檢查，如果他們總和是0。不喜歡優化的解決方案llok到我。

看了網上看了一下類似的問題，看起來它可以用下面的程序來動態編程來解決找到有沒有組合存在做和11就是一個例子嗎？

public boolean subsetSum(int input[], int total) { 

     boolean T[][] = new boolean[input.length + 1][total + 1]; 
     for (int i = 0; i <= input.length; i++) { 
      T[i][0] = true; 
     } 

     for (int i = 1; i <= input.length; i++) { 
      for (int j = 1; j <= total; j++) { 
       if (j - input[i - 1] >= 0) { 
        T[i][j] = T[i - 1][j] || T[i - 1][j - input[i - 1]]; 
       } else { 
        T[i][j] = T[i-1][j]; 
       } 
      } 
     } 
     return T[input.length][total]; 

    } 




public static void main(String args[]) { 
    TestDynamic ss = new TestDynamic(); 
    int arr1[] = {2, 3, 7, 8}; 
    System.out.print(ss.subsetSum(arr1, 11)); 

}

，但我不知道如何上面PROGRAME擴展到

1）包括負數
2）找到的元素組合whick使之和爲零（上述程序只是認定其是否可能使給定的總和，但不找到哪一組數字使其爲零）

來源

2016-07-28 emilly

http://stackoverflow.com/questions/15532957/to-find-a-subset-from-a-set-whose-sum-equals-to-zero –

@ErwinRooijakkers解決方案在您提供的鏈接不完整並且是非常高的水平。我無法理解它至少 – emilly

試試這個：http://codereview.stackexchange.com/questions/36214/find-all-subsets-of-an-int-array-whose-sums-equal-a-given-target ）。 –

這裏是在Javascript中的完整實現。你可以用node.js來運行它。

function target_sum(a, k, x) 
{ 
    if (k == a.length) return []; 
    if (a[k] == x) { 
     return [[a[k]]]; 
    } else { 
     var s = target_sum(a, k + 1, x);  // not using a[k] 
     var t = target_sum(a, k + 1, x - a[k]); // using a[k] 
     for (var i = 0; i < t.length; ++i) { 
      t[i].unshift(a[k]); // a[k] is part of the solution 
      s.push(t[i]);  // merge t[] into s[] 
     } 
     return s; 
    } 
} 

var s = target_sum([1,4,5,2,7,8,-3,-5,-6,9,3,-7,-1,5,6], 0, 0); 
for (var i = 0; i < s.length; ++i) 
    console.log(s[i].join(","));

請注意，這是一種指數算法。不要在大型陣列上使用它。

Erwin Rooijakkers也指出了正確的方向。特別是，this post給出了另一種算法。我對以下內容可能是錯誤的 - 我相信算法會爲空間換取速度。它避免了將數組暫存到調用堆棧中，但它必須做更多的遞歸來實現這一點。

編輯：關於你提到的算法。它不是指數型的，但如果我是對的，它只適用於正數。其時間複雜度也與目標總和成正比，根據輸入可能不理想。

來源

2016-07-29 00:22:32 user172818

從正負數集合中找出所有可能的子集總和等於0？

回答

相關問題