从正负数集合中找出所有可能的子集总和等于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？

回答

相关问题