从正数和负数集合中找出所有可能的等于0的子集和？[副本]

Question

如果有一个包含一组正数和负数的数组，请打印所有等于0的子集和。

我可以想出一种方法，在那里我可以制作givcen阵列的所有功率集，并检查它们的总和是否为0。但对我来说，这不像是优化的解决方案。

看完网上看起来有点类似的问题，好像可以用下面的程序动态编程来解决，看看是否有组合存在，让和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));

}

但是我不知道如何将上述程序扩展到

1）包括负数
2）找到使和为零的元素组合（上面的程序只是发现它是否可以使给定的和，但没有找到哪一组数字使它为零）

Answer 1

下面是Javascript的完整实现。您可以使用节点运行它。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(","));

注意这是指数算法，不要在大数组上使用。

欧文·鲁伊贾克斯也指出了正确的方向。特别是，这篇文章给出了另一种算法。我可能在以下几点上错了——我认为算法以速度换取空间。它避免了将数组转移到调用堆栈中，但必须执行更多的递归才能实现这一点。

编辑：关于你提到的算法。它不是指数型的，但如果我是对的，它只适用于正数。它的时间复杂度也与目标和成比例，目标和根据输入可能不理想。