algorithm - 是否可以在线性时间 O(n) 或 O(nlogn) 中计算

Question

我试图在 O(n) 或 O(n log n) 中找到一种方法来在以下情况下返回输出。如果我有一个包含 n 个元素的集合，并且我需要在集合中找到最小的数字集合，它加起来等于给定的数字。

例如，A=[0,9,1,2,5,4]，如果给定我的 q=6，那么我可能的组合是：(2+4)、(1+5) 并且应该返回 null 如果没有找到适当的子集？，这不是一个家庭作业问题，我只是想学习好的编程方法。

Answer 1

一般问题是http://en.wikipedia.org/wiki/Subset_sum_problem。

据我们所知，没有多项式速度算法可以解决该问题，并且相信不存在。但是，存在一些很好的近似方法。