该款项子集的问题指出:
给定一组整数,是否有一个非空子集,其总和为零？
这个问题一般是NP完全的.我很好奇这个轻微变体的复杂性是否已知:
给定一组整数,是否有一个大小
k的子集,其总和为零？
例如,如果k = 1,您可以执行二进制搜索以查找答案O(log n).如果k = 2,则可以将其归结为O(n log n)(例如,请参阅查找一个数组中的一对元素,其总和等于给定数字).如果k = 3,则可以这样做O(n^2)(例如,参见查找数组中的三个元素,其总和最接近给定数字).
是否有一个已知的界限可以作为一个函数放在这个问题上
k？
作为动机,我正在考虑这个问题你如何将一个数组分成两部分,使这两部分具有相同的平均值？并试图确定它是否实际上是NP完全的.答案在于是否存在如上所述的公式.
除非采用一般解决方案,否则我非常有兴趣知道最佳约束k=4.