这是一道面试题,所以我觉得应该有解法,但是不知道是什么,也找不到。
问题是这样的:
给定一个数字数组,检查是否有可能在任意位置进行加法和减法,使总和为零。
例如:
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)
最佳答案
让我们称您的号码为 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)。
结论:阅读有关这些问题的维基百科文章,您会在那里找到所有信息。
关于python - 检查通过元素的 + 和 - 的任意组合,数组总和是否为零,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31635886/