萨姆在阵列的任何k个元素的若干

设计的算法，给定n个整数的集合S和其他整数x，判断是否不存在K的（N> K> 2）元素S的总和恰好是x。请给出您的运行时间算法萨姆在阵列的任何k个元素的若干

我一直在准备面试，而且我遇到了这个算法。我已经解决了问题中指定了k的问题。像2或3.但我找不到答案，我可能会解决任何可能存在的k。我试图用动态编程来解决它，但没有得到结果。谁可以帮我这个事。

从集合S正整数，也可以是负的也？ – user502144 2014-10-17 17:58:13

这篇文章是否解决您的问题？ http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/ – user502144 2014-10-17 18:00:37

您可以制作一个尺寸为x的int阵列cnt，然后通过该集合并标记可达点。 cnt的所有元素初始设置为-1，除了设置为零的元素零。

重复为每个元素的Ssi相同的过程：在i位置的cnt每个元素是非负的，检查元件cnt[i+si]（如果它是该阵列的边界内）。如果是，请将其设置为cnt[si+i] = max(cnt[i]+1, cnt[si+i])。

一旦您浏览了S的所有元素，请检查cnt[x]。如果设置为两个或更多，则存在S中两个或更多个元素的组合，总计为x。

这种算法是伪多项式，随着运行时间O(x*|S|)

2014-10-17 17:51:04 dasblinkenlight

回答