該款項(xiàng)子集的問題指出：給定一組整數(shù)，是否存在一個總和為零的非空子集？通常，此問題是NP完全的。我很好奇這個輕微變體的復(fù)雜性：給定一組整數(shù)，是否存在大小k和的總和為零的子集？例如，如果k = 1您可以進(jìn)行二進(jìn)制搜索以找到答案O(log n)。如果為k = 2，則可以將其簡化為O(n log n)（例如，請參見從總和等于給定數(shù)的數(shù)組中查找一對元素）。如果為k = 3，則可以執(zhí)行此操作O(n^2)（例如，請參見在數(shù)組中求和最接近給定數(shù)字的三個元素）。是否存在一個已知的界限可以作為函數(shù)來解決這個問題k？出于動機(jī)，我在考慮這個問題，如何將一個數(shù)組分成兩部分，以使這兩部分的平均值相等？并嘗試確定它是否實(shí)際上是NP完整的。答案在于是否存在上述公式。除非有一般解決方案，否則我對了解的最佳界限會非常感興趣k=4。