具有固定子集大小的Sum子集

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个最小元素和2个最大元素开始,以非递减顺序计算lesser2个元素(a[i] + a[j])的所有greater和,(a[k] + a[l])以非递增顺序计算2个元素的所有和.lesser如果总和小于零则增加总和,如果总和大于零则减少greater1,当总和为零(成功)或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'的数组.仅使用"j"的值就足够了,比"i"更大.
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值总和预先计算一个bitset .并用它来检查其他k/2值的总和.时间复杂度为O(n ^(ceil(k/2))).

Answer 2

时间复杂度很简单O(n^k)（元素k中 - 大小的子集的数量n）。

由于k是给定的常数，（可能是相当高阶的）多项式上限作为 的函数的复杂性n。