给定一个 N 非负整数列表，提出一个算法来检查列表中 X 个数字的总和是否等于剩余的 N-X.
换句话说，Subset sum problem 的一个更简单的例子这涉及整个集合。
一个尝试的解决方案
按降序排列列表的元素。将变量 SUM 初始化为第一个元素。删除第一个元素(最大的 a(1))。令 a(n) 表示当前列表中的 n-th 元素。
虽然列表有多个元素，
使
SUM等于SUM + a(1)或SUM - a(1)，取最接近a(2)。 (最接近的意思是|a(2) - SUM_POSSIBLE|是最小值)。删除
a(1)。
如果SUM等于-a(1)或a(1)，则存在线性和。
问题
我似乎无法解决上述算法，如果它是正确的，我想要一个证明。 如果错误(更有可能)，是否有办法在线性时间内完成此操作？
PS:如果我做错了什么请原谅:S
最佳答案
请注意，您希望 x 个数字的总和等于其他 N-x 个数字的总和。
你可以通过说你想看看是否有一个总和为 S/2 的子集来简化它，其中 S 是整个集合的总和。
因此，您可以计算一次迭代所需的总和 (O(n))。
然后只需使用已知算法，如 Knapsack 找到满足您总和的子集。
另一个更“数学”的解释: Dynamic Programming – 3 : Subset Sum
编辑:
作为对您其他问题的回答，您的算法是错误的。考虑这个数字列表:
{3,3,4,4}
总和为 14，因此您正在寻找总和为 7 的子集。显然它将是 3+4。
检查完 2 个 3 之后，您的算法将返回 false
关于检查线性和为零的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11707179/