我一直在解决Subset_sum_problem。
给定一组整数（S），需要计算总和等于给定目标（T）的非空子集。
示例：给定集合，S{4, 8, 10, 16, 20, 22} 目标，T = 52。
约束：集合 S 的元素 N 的数量限制为 8。因此，NP 时间解是可以接受的，因为 N 的上限很小。时间和空间的复杂性并不是真正的问题。
输出：
总和正好等于 T=52 的可能子集是：
{10、20、22}
{4、10、16、22}
Wiki 和其他一些页面中给出的解决方案试图检查是否存在这样的子集（是/否）。
如上例所述，计算所有可能的子集并没有真正的帮助。
此链接上的动态编程方法提供了单个这样的子集，但我需要所有这些子集。
一种明显的方法是使用蛮力计算所有 2^N 组合，但这将是我最后的手段。
我正在寻找一些程序示例（最好是 C++）或算法来计算这些带有插图/示例的子集？
如果 N <= 8 为什么不使用 2^n 解决方案？只有 256 种可能性会非常快
当您为子集和问题构建动态规划表时，您会像这样初始化其中的大部分（取自问题中引用的 Wikipedia 文章）：
Q(i,s) := Q(i - 1,s) 或 (xi == s) 或 Q(i - 1,s - xi)
这会将表格元素设置为 0 或 1。
这个简单的公式不能让您区分可以给您 1 的几种情况。
但是您可以改为将 table 元素设置为可以区分这些情况的值，如下所示：
Q(i,s) := {Q(i − 1,s) != 0} * 1 + {xi == s} * 2 + {Q(i − 1,s − xi) != 0} *4
然后你可以从最后一个元素开始遍历表格。在每个元素处，元素值将告诉您是否有零、一条或两条可能的路径及其方向。所有路径都会为您提供总和为 T 的所有数字组合。最多为 2 N。
只是蛮力的。如果 N 限制为 8，那么您的子集总数为 2^8，即只有 256 个。它们给出限制是有原因的。
您可以将集合包含表示为二进制字符串，其中每个元素要么在集合中，要么在集合外。然后你可以只增加你的二进制字符串（可以简单地表示为一个整数），然后使用按位 & 运算符确定哪些元素在集合中。一旦你数到了 2^N，你就知道你已经完成了所有可能的子集。
最好的方法是使用动态编程方法。但是，动态编程只是回答子集总和是否存在，如您在问题中提到的那样。
通过动态规划，您可以通过回溯输出所有解决方案。但是，生成所有有效组合的总体时间复杂度仍然是 2^n。
因此，任何比 2^n 更好的算法都几乎是不可能的。
UPD：来自@Knoothe 评论：您可以修改horowitz-sahni 的算法以枚举所有可能的子集。如果存在M总和等于的此类集合S，则总体时间复杂度在O(N * 2^(N/2) + MN)