具有固定子集大小的Sum子集
求和子集问题指出：
给定一组整数，是否有一个总和为零的非空子集？
这个问题通常是NP完全的。 我很好奇，如果这个轻微的变种的复杂性是已知的：
给定一组整数，是否有一个总和为零的大小为
k的子集？
例如，如果k = 1 ，则可以执行二进制search以在O(log n)find答案。 如果k = 2 ，那么你可以把它归结为O(n log n) （例如参见从一个数组中找出一对元素，其和等于一个给定的数字 ）。 如果k = 3 ，那么你可以做O(n^2) （例如参见在一个数组中find三个元素的总和最接近给定的数字 ）。
作为
k一个函数，是否有一个可以放在这个问题上的已知边界？
作为动机，我正在考虑这个问题。 你如何将一个数组分成两部分，这两部分的平均数是相等的？ 并试图确定它是否实际上是NP完整的。 答案在于是否有如上所述的公式。
除了一个通用的解决scheme，我会非常有兴趣知道k=4的最优界限。
对于k = 4，空间复杂度O（n），时间复杂度O（n 2 * log（n））
sorting数组。 从2个最小元素和2个最大元素开始，计算非递减顺序的2个元素(a[i] + a[j])所有lesser和，以及2个元素(a[k] + a[l])在不增加的顺序。 如果总和小于零，则减小总和，如果总和大于零减小，当总和为零（成功）或a[i] + a[j] > a[k] + a[l] （失败）。
诀窍是以这样的方式遍历所有索引i和j ，即(a[i] + a[j])永远不会减less。 对于k和l ， (a[k] + a[l])绝不应该增加。 优先队列有助于做到这一点：
- 把
key=(a[i] + a[j]), value=(i = 0, j = 1)放到优先级队列中。 - Pop
(sum, i, j)来自优先队列。 - 在上面的algorithm中使用
sum。 - 只有当这些元素不是已经存在时，将
(a[i+1] + a[j]), i+1, j和(a[i] + a[j+1]), i, j+1用过的。 为了跟踪使用的元素，为每个“i”维护一个最大使用的“j”数组。 仅仅使用“j”的值比“i”更大就足够了。 - 从第2步继续。
对于k> 4
如果空间复杂度被限制为O（n），我找不到任何更好的东西，比使用蛮力的k-4值和上述algorithm的其余4值。 时间复杂度O（n （k-2） * log（n））。
对于非常大的k 整数线性规划可能会有所改进。
更新
如果n非常大（与最大整数值的顺序相同），则可以实现O（1）优先级队列，从而提高O（n 2 ）和O（n （k-2） ）的复杂性。
如果n >= k * INT_MAX ，则具有O（n）空间复杂度的不同algorithm是可能的。 预先计算所有可能的k/2值的和。 并用它来检查其他k/2值的总和。 时间复杂度是O（n （ceil（k / 2）） ）。
确定W + X + Y + Z = {w + x + y + z |中是否为0的问题 w中的w，x中的x，y中的y，Z中的z}基本上相同，除了不具有烦人的退化情况（即，问题是用最less资源相互缩减的）。
这个问题（并且因此原始的k = 4）具有O（n ^ 2 log n）时间，O（n） – 空间algorithm。 对于k = 2（以确定A + B中的0）的O（n log n）时间algorithm以sorting顺序访问A并且以逆序sorting顺序访问B。 因此，我们需要的是一个O（n）空间迭代器，对于A = W + X，对于B = Y + Z可以对称地重复使用。令W = {w1，…，wn}为sorting顺序。 对于X中的所有x，将一个键值项（w1 + x，（1，x））插入到优先级队列中。 重复删除min元素（wi + x，（i，x））并插入（wi + 1 + x，（i + 1，x））。
这个问题很相似：
这个子集和问题的变体是否更容易解决？
它仍然是NP完整的。
如果不是，子集和也将在P中，因为它可以表示为F(1) | F(2) | ... F(n) F(1) | F(2) | ... F(n) F(1) | F(2) | ... F(n)其中F是你的函数。 这将有O(O(F(1)) + O(F(2)) + O(F(n))) ，这仍然是多项式，这是不正确的，因为我们知道它是NP完全。
请注意，如果您在input上有一定的界限，则可以实现多项式时间。
还要注意，蛮力运行时间可以用二项式系数来计算。
O（n ^ 2log（n））中k = 4的解
步骤1：计算两两和，并对列表进行sorting。 有n（n-1）/ 2个和。 所以复杂度是O（n ^ 2log（n））。 保持总和的个人的身份。
步骤2：对于上面列表中的每个元素，search补码并确保它们不共享“个体”。有n ^ 2次search，每次search的复杂度为O（log（n））
编辑：原始algorithm的空间复杂度是O（n ^ 2）。 通过模拟虚拟2Dmatrix（O（n），如果考虑空间来存储数组的sorting版本），可以将空间复杂度降低到O（1）。
首先关于二维matrix：对数字进行sorting并使用两两和来创buildmatrixX. 现在matrix是这样一种方式，所有的行和列都被sorting。 要在这个matrix中search一个值，search对angular线上的数字。 如果数字在X [i，i]和X [i + 1，i + 1]之间，则基本上可以将search空间减半到matrixX [i：N，0：i]和X [0：i ，i：N]。 由此产生的searchalgorithm是O（log ^ 2n）（我不是很确定，有人可以检查它吗？）。
现在，不是使用实数matrix，而是使用虚拟matrix，其中X [i，j]是根据需要计算的，而不是预先计算它们。
产生的时间复杂度：O（（nlogn）^ 2）。
PS：在下面的链接中，它说二维sortingmatrixsearch的复杂度是O（n）复杂度。 如果这是真的（即O（log ^ 2n）不正确），那么最终的复杂度是O（n ^ 3）。
时间复杂度平均为O(n^k) （ n元素的k个子集的数量）。
由于k是一个给定的常数，一个（可能相当高阶的）多项式将复杂度作为n的函数上界。
要build立awesomo的答案…如果我们可以假设数字sorting，对于给定的k，我们可以比O（n ^ k）做得更好; 简单地取所有大小为（k-1）的O（n ^（k-1））个子集，然后在剩余的数字中进行二分search，当添加到第一个（k-1）时，给出目标。 这是O（n ^（k-1）log n）。 这意味着复杂性肯定比这less。
事实上，如果我们知道k = 3的复杂度是O（n ^ 2），那么对于k> 3我们可以做得更好：select所有（k-3） – 子集，其中有O（n ^ k-3）），然后解决其余元素的O（n ^ 2）问题。 对于k> = 3，这是O（n ^（k-1））。
但是，也许你可以做得更好？ 我会考虑这个。
编辑：我最初要增加很多提出不同的承担这个问题，但我已经决定发布删节版本。 我鼓励其他海报看他们是否相信这个想法有什么价值。 分析是艰难的，但它可能只是足够疯狂的工作。
我们可以使用固定的k这个事实，并且奇数和偶数的和以某种方式performance，定义一个recursionalgorithm来解决这个问题。
首先，修改问题，使得列表中有偶数和奇数（如果二者均为偶数，则可以通过除以2来实现，或者如果所有都是奇数，则可以通过从目标总和中减去1来实现，并且重复有必要的）。
接下来，使用偶数个奇数就可以达到目标和的事实，只用奇数个奇数就可以达到奇数目标和。 生成奇数的适当子集，并使用偶数recursion地调用algorithm，总和减去被检查的奇数子集的总和，并且k减去奇数子集的大小。 当k = 1时，进行二分search。 如果有k> n（不确定这是否会发生），则返回false。
如果你有很less的奇数，这可以让你很快地选出必须是获胜子集的一部分，或丢弃那些不能成功的子集。 你可以通过使用减法技巧将许多偶数的问题转换成大量奇数的等价问题。 因此，最糟糕的情况是，偶数和奇数的数量非常相似，这就是我现在所处的位置。 一个无用的松散的上界是比蛮力更糟的数量级，但我觉得这可能至less和蛮力一样好。 受欢迎的思想！
编辑2：上面的例子，为了说明。
{1, 2, 2, 6, 7, 7, 20}, k = 3, sum = 20. Subset {}: {2, 2, 6, 20}, k = 3, sum = 20 = {1, 1, 3, 10}, k = 3, sum = 10 Subset {}: {10}, k = 3, sum = 10 Failure Subset {1, 1}: {10}, k = 1, sum = 8 Failure Subset {1, 3}: {10}, k = 1, sum = 6 Failure Subset {1, 7}: {2, 2, 6, 20}, k = 1, sum = 12 Failure Subset {7, 7}: {2, 2, 6, 20}, k = 1, sum = 6 Success
