有一个固定的子集大小总和子集 [英] Sum-subset with a fixed subset size

问题描述

借助总和子集的问题规定：

给出一个整数集，是有一个非空的子集，其总和为零？

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

这个问题是NP完全的总称。我很好奇，如果这种轻微变形的复杂性是众所周知的：

This problem is NP-complete in general. I'm curious if the complexity of this slight variant is known:

给出一个整数集，是有大小的一个子集 K 的总和为零？

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）的（如见<一href="http://stackoverflow.com/questions/4720271/an-interview-question-of-microsoft-about-finding-pair-of-elements-from-array-who">An微软的面试问题关于发现对元素的数组，其总和也同样给定数字）。如果 K = 3 ，那么你可以做为O（n ^ 2）（如见<一href="http://stackoverflow.com/questions/2070359/finding-three-elements-in-an-array-whose-sum-is-closest-to-an-given-number">Finding在一个数组，其总和最接近于给定数目的）。三个元素

For example, if k = 1, you can do a binary search to find the answer in O(log n). If k = 2, then you can get it down to O(n log n) (e.g. see An interview question of Microsoft about finding pair of elements from array whose sum equally a given number). If k = 3, then you can do O(n^2) (e.g. see Finding three elements in an array whose sum is closest to an given number).

是否存在已知的绑定，可以放置在这个问题上的一个函数 K ？

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

作为动力，我在想这个问题，<一个href="http://stackoverflow.com/questions/8914961/how-do-you-partition-an-array-into-2-parts-such-that-the-two-parts-have-equal-av">How你分区阵列分为两部分，使得所述两个部分具有相等的平均？的，并试图确定它是否实际上是NP完全问题。答案在于是否存在如上所述的公式。

As motivation, I was thinking about this question How do you partition an array into 2 parts such that the two parts have equal average? and trying to determine if it is actually NP-complete. The answer lies in whether or not there is a formula as described above.

除非一个通用的解决方案，我会在明知开往最佳很感兴趣 K = 4 。

Barring a general solution, I'd be very interested in knowing an optimal bound for k=4.

推荐答案

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

For k=4, space complexity O(n), time complexity O(n² * log(n))

排序数组。从2最小2起最大的因素，计算所有较小 2元款项（A [I] + A [J]）在非降序排列，所有大于的2个元素款项（一[K] + A [L]）在非递增次序。增加较小之和，如果总和小于零，降低更大，如果一个总和大于零，停车时总和是零（成功）或 A [1] +一[J]≥一[K] + A [L] （失败）。

Sort the array. Starting from 2 smallest and 2 largest elements, calculate all lesser sums of 2 elements (a[i] + a[j]) in the non-decreasing order and all greater sums of 2 elements (a[k] + a[l]) in the non-increasing order. Increase lesser sum if total sum is less than zero, decrease greater one if total sum is greater than zero, stop when total sum is zero (success) or a[i] + a[j] > a[k] + a[l] (failure).

关键是要遍历所有的指标我和Ĵ以这样的方式，即（A [I] + A [J]）绝不会减少。而对于 K 和→，（一[K] + A [L]）不应该增加。优先级队列有助于做到这一点：

The trick is to iterate through all the indexes i and j in such a way, that (a[i] + a[j]) will never decrease. And for k and l, (a[k] + a[l]) should never increase. A priority queue helps to do this:

1. 把键=（A [I] + A [J]），值=（I = 0，J = 1）优先级队列中。
2. 在弹出（总和，I，J）从优先级队列中。
3. 使用上述算法总和。
4. 把（A [1 + 1] + A [J]），I + 1，J 和（A [1] +一[J + 1]），I，J + 1 来优先队列仅当没有已经使用了这些元素。为了跟踪使用的元素，保持最大的用'J'的每个'我'的数组。它是足够使用只值'J'，这是更大的，不是'我'。
5. 从第2步继续。

1. Put key=(a[i] + a[j]), value=(i = 0, j = 1) to priority queue.
2. Pop (sum, i, j) from priority queue.
3. Use sum in the above algorithm.
4. Put (a[i+1] + a[j]), i+1, j and (a[i] + a[j+1]), i, j+1 to priority queue only if these elements were not already used. To keep track of used elements, maintain an array of maximal used 'j' for each 'i'. It is enough to use only values for 'j', that are greater, than 'i'.
5. Continue from step 2.

对k> 4

如果空间复杂度被限制到为O（n），我找不到更好的东西，不是使用蛮力的 K-4 值和上述算法对其余 4 值。时间复杂度为O（n ^（K-2） *的log（n））。

If space complexity is limited to O(n), I cannot find anything better, than use brute force for k-4 values and the above algorithm for the remaining 4 values. Time complexity O(n^(k-2) * log(n)).

对于非常大的 K 整数线性规划可能给予一定的提升。

For very large k integer linear programming may give some improvement.

更新

如果 N 是非常大的（相同的顺序最大整数值上），就可以实现O（1）优先级队列，提高了复杂性来为O（n ² ）和O（N ^（K-2））。

If n is very large (on the same order as maximum integer value), it is possible to implement O(1) priority queue, improving complexities to O(n²) and O(n^(k-2)).

如果 N'GT = K * INT_MAX ，不同的算法为O（n）的空间复杂度是可能的。 precalculate一个bitset为 K / 2 值的所有可能的总和。并用它来检查其它 K / 2 值总和。时间复杂度为O（n ^{（CEIL（K / 2））}）。

If n >= k * INT_MAX, different algorithm with O(n) space complexity is possible. Precalculate a bitset for all possible sums of k/2 values. And use it to check sums of other k/2 values. Time complexity is O(n^(ceil(k/2))).

这篇关于有一个固定的子集大小总和子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！