arrays - 查找具有给定总和的 K 个元素的子序列

Question

可能的重复：
具有固定子集大小的 Sum-subset

所以我有一个数组A，有元素A[1], A[2] .. A[N]

我想找到一个子序列（不一定是连续的），正好有K元素，其总和正好是Sum.

我最好的猜测是 O(N ^K )，如果你运行 K 个嵌套循环，并测试每一种可能性。

这可以更快地完成吗？

的所有元素A都是整数，大于 0。

Answer 1

我认为这不能在多项式时间内解决。@Anderson 是对的，它确实类似于背包问题。

虽然您可以通过分支定界算法使其更快，但它的有效性将基于您的实际值。（例如：如果超过总和，则不要进一步测试）

编辑： 基于主题，@amit 链接的内容，O(n^k) 确实是最佳答案，对于任何固定的 k 值，它是 n 中的多项式。