假设我有一组大小为 n 的有限数值。
问题：是否有一种有效的算法来枚举该集合的 k 组合，以便组合 I 先于组合 J，如果 I 中的元素之和小于或等于 J 中元素的总和？
显然，可以简单地枚举组合并根据它们的总和对它们进行排序。 但是，如果集合很大，则所有组合的暴力枚举（更不用说排序）将不可行。 如果我只对获得按总和排名的前m<<选择（n，k）组合感兴趣，是否有可能在宇宙热寂之前获得它们？
没有多项
式算法可以通过这种方式枚举集合（除非 P=NP）。
如果有这样的算法（让它成为 A），那么我们可以多项式解决子集和问题：
- 运行 A
- 执行二分搜索以查找总和最接近所需数字的子集。
请注意，步骤 1 以多项式方式运行（假设），步骤 2 以 O(log(2^n)) = O(n) 运行。
结论：由于子集和问题是NP完全的，有效地求解这个问题将证明P=NP - 因此这个问题没有已知的多项式解。
编辑：即使问题是NP-Hard，也可以通过选择最小的m元素，从这些m元素生成所有子集 - 并选择其中最小的m，O(n+2^m)上获得"最小"m子集。因此，对于相当小的m值 - 计算它可能是可行的。