python - 检查通过元素的 + 和 - 的任意组合，数组总和是否为零

Question

The source of the question .

这是一道面试题，所以我觉得应该有解法，但是不知道是什么，也找不到。

问题是这样的:

给定一个数字数组，检查是否有可能在任意位置进行加法和减法，使总和为零。

例如:

A={2,1,8,5}

+2-1+8+5 != 0

-2-1+8+5 != 0

+2-1-8+5 != 0

-2-1+8-5 == 0

这样就完成了。

我已经有了指数解的代码:

def isFeasible(A, p, _sum):
    if p == len(A):
        if _sum==0: return True
        else: return False;

    return (isFeasible(A, p+1, _sum+A[p]) or isFeasible(A, p+1, _sum-A[p]))


def driver(arr):
    print isFeasible(arr,0,0)

Answer 1

让我们称您的号码为 A[i] i = 1..N。您需要求解以下等式:

  sum(X[i] * A[i]) = 0,   for X[i] = -1 or 1

显然，这等同于(只需将 X[] 中的 -1 更改为 0):

  sum(X[i] * 2*A[i]) = sum(A[i]),   for X[i] = 0 or 1

第二个问题正是partition problem对于数字 (A[i])，即 NP-hard如果数字是任意的。此外，分区问题是众所周知的最简单的情况 knapsack problem .只需阅读这两篇维基百科文章，您就会学到很多解决问题的方法。

编辑:另一个等价的问题是:

  sum(X[i] * A[i]) = sum((1 - X[i]) * A[i])    for X[i] = 0 or 1

和第二个等式一样，但是现在可以清楚的看出这是一个划分问题:X[i] = 1表示把元素放在左边，X[ i] = 0 表示将元素放在右边。所有元素放入后，总和必须相等。

另请注意，有一个伪多项式解 here , 它也可以变成 fully polynomial approximation scheme .另请注意，背包问题可以通过 meet-in-the-middle approach 解决，这将指数求解的时间复杂度从 O(2^N) 降低到 O(sqrt(2)^N)。

结论:阅读有关这些问题的维基百科文章，您会在那里找到所有信息。