algorithm - 计算给定总和的所有子集 - Java

Question

我有一个list不同的正整数数组，代表一个集合L和一个整数S。L计算其元素之和等于 的所有子集的最快方法是什么S，而不是遍历所有子集并仅检查每个子集的和是否等于S？

Answer 1

这可以通过O(NS)使用类似于背包问题的简单动态规划方法来解决。让我们Q为每个i解决以下问题：存在多少个第一个i元素的子集，L使得它们的总和等于Q。让我们表示这些子集的数量C[i,Q]。

显然C[0,0]=1，C[0,Q]=0对于Q!=0. （注意，i=0表示前 0 个元素，即没有元素。）

对于更大的i我们有两种可能性：要么将最后一个可用元素 ( L[i-1]) 带到我们的集合中，然后我们就有C[i-1, Q-L[i-1]]这样的集合。要么不采取，那么我们就有C[i-1, Q]这样的集合。因此，C[i,Q]=C[i-1, Q-L[i-1]]+C[i-1, Q]。迭代i和Q，我们计算所有Cs。

请注意，如果 中的所有元素L都是非负的，那么您只能解决非负Qs 的问题，如果 ，则第一项消失Q<L[i-1]。如果允许负元素，那么您也需要考虑负Qs。