子集大小固定的总和子集

Question

该款项子集的问题指出：给定一组整数，是否存在一个总和为零的非空子集？通常，此问题是NP完全的。我很好奇这个轻微变体的复杂性：给定一组整数，是否存在大小k和的总和为零的子集？例如，如果k = 1您可以进行二进制搜索以找到答案O(log n)。如果为k = 2，则可以将其简化为O(n log n)（例如，请参见从总和等于给定数的数组中查找一对元素）。如果为k = 3，则可以执行此操作O(n^2)（例如，请参见在数组中求和最接近给定数字的三个元素）。是否存在一个已知的界限可以作为函数来解决这个问题k？出于动机，我在考虑这个问题，如何将一个数组分成两部分，以使这两部分的平均值相等？并尝试确定它是否实际上是NP完整的。答案在于是否存在上述公式。除非有一般解决方案，否则我对了解的最佳界限会非常感兴趣k=4。

Answer 1

对于k = 4，空间复杂度O（n），时间复杂度O（n ² * log（n））

对数组进行排序。从最小的2个元素和最大lesser的2个元素开始(a[i] + a[j])，以非递减顺序计算2个元素的所有greater和，(a[k] + a[l])并以非递增顺序计算2个元素的所有和。lesser如果总和小于零，则增加总和；如果总和大于零，则增加greater一；如果总和为零（成功）或a[i] + a[j] > a[k] + a[l]（失败），则停止。

诀窍是遍历所有索引，i并且j这种方式(a[i] + a[j])永远不会减少。并且对于k和l，(a[k] + a[l])永远不应该增加。优先级队列有助于实现此目的：

1. 放入key=(a[i] + a[j]), value=(i = 0, j = 1)优先级队列。

2. (sum, i, j)从优先级队列中弹出。

3. 使用sum上述算法。

4. 把(a[i+1] + a[j]), i+1, j和(a[i] + a[j+1]), i, j+1优先级队列仅如果不已经使用了这些元素。为了跟踪使用过的元素，请为每个“ i”维护一个最大使用的“ j”数组。仅使用大于“ i”的“ j”值就足够了。

5. 从步骤2继续。

对于k> 4

如果将空间复杂度限制为O（n），那么我将无法找到比将蛮力用于k-4值并将上述算法用于剩余4值更好的方法。时间复杂度O（n ^（k-2） * log（n））。

对于非常大的k 整数，线性规划可能会有所改善。

更新资料

如果n非常大（与最大整数值相同的顺序），则可以实现O（1）优先级队列，从而提高O（n ²）和O（n ^（k-2））的复杂度。

如果为n >= k * INT_MAX，则可以使用具有O（n）空间复杂度的其他算法。为所有可能的k/2值之和预先计算一个位集。并使用它来检查其他k/2值的总和。时间复杂度为O（n ^{（ceil（k / 2））}）。