algorithm - 具有固定子集大小的 Sum-subset

Question

sum-subset problem状态:

Given a set of integers, is there a non-empty subset whose sum is zero?

这个问题通常是 NP 完全问题。我很好奇这种轻微变体的复杂性是否已知:

Given a set of integers, is there a subset of size k whose sum is zero?

例如，如果k = 1，您可以进行二进制搜索以在O(log n) 中找到答案。如果 k = 2，那么您可以将其降低到 O(n log n)(例如，参见 Find a pair of elements from an array whose sum equals a given number)。如果 k = 3，那么您可以执行 O(n^2)(例如，参见 Finding three elements in an array whose sum is closest to a given number)。

Is there a known bound that can be placed on this problem as a function of k?

作为动力，我在想这个问题How do you partition an array into 2 parts such that the two parts have equal average?并试图确定它是否真的是 NP 完全的。答案在于是否存在上述公式。

除非有通用解决方案，否则我很想知道 k=4 的最佳界限。

Answer 1

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

对数组进行排序。从 2 个最小和 2 个最大的元素开始，以非递减顺序计算 2 个元素 (a[i] + a[j]) 的所有 lesser 和，所有 code>greater 2 个元素 (a[k] + a[l]) 的非递增顺序之和。如果总和小于零，则增加 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 使用上述算法更好的方法了> 值(value)观。时间复杂度 O(n^(k-2) * log(n)).

对于非常大的k integer linear programming可能会有所改善。

更新

如果 n 非常大(与最大整数值在同一顺序)，则可以实现 O(1) 优先级队列，将复杂度提高到 O(n²) 和 O(n^(k-2)).

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