子集总和问题的有趣变化

Question

一位工作中的朋友向我提出了一个有趣的子集问题的变化：

给定一组正整数，大小为n和整数A和K 正是一个元素, ，谁的总和等于k？

他声称这可以通过时间复杂性o（NKA）来完成，我无法提出一种动态的编程算法，该算法实现了这一运行时间。可以做吗？

Answer 1

如果k和a足够小，可以做到这一点，以便我们声明一个数组

bool found[a][k]

您将迭代s中的每个值，并在 成立 阵列获得新状态。

说，对于a = 1和k = 7的索引，s的当前值为7，

如果发现[1] [7]是正确的，那么您也可以确保找到[2] [14]也是正确的。

当迭代结束时，您需要做的就是检查[a] [k]是正确的。

Answer 2

令S = {S1， ldots，sn}

令P（j，k，a）为真，如果可以在s1， ldots，sj中找到总和至k的元素。

然后P（J，K，A）= P（J-1，K-SJ，A-1）或P（J，K，A）（需要SJ或不需要SJ）。

然后，该算法包括将尺寸n的3-D表填充k+1的尺寸n+1。每个条目都需要恒定的时间来填充，因此时间（和空间）的复杂性为O（NKA）