计算给定总和的所有子集 - Java
Count all subsets with given sum - Java
我有一个数组 list，其中包含代表一组 L 的不同正整数，以及一个整数 S。计算 L 的所有元素总和等于 S 的子集的最快方法是什么，而不是遍历所有子集并仅检查每个子集的总和是否等于 S ]？
这可以在 O(NS) 中使用简单的动态规划方法解决，类似于背包问题。让我们对每个 Q 和每个 i 解决以下问题：L 的前 i 个元素存在多少个子集，使得它们的总和等于 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中的所有元素都是非负的，那么只对非负的Q就可以解题，如果Q<L[i-1]第一项消失.如果允许负元素，那么你也需要考虑负 Qs。
我有一个数组 list，其中包含代表一组 L 的不同正整数，以及一个整数 S。计算 L 的所有元素总和等于 S 的子集的最快方法是什么，而不是遍历所有子集并仅检查每个子集的总和是否等于 S ]？
这可以在 O(NS) 中使用简单的动态规划方法解决，类似于背包问题。让我们对每个 Q 和每个 i 解决以下问题：L 的前 i 个元素存在多少个子集，使得它们的总和等于 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中的所有元素都是非负的，那么只对非负的Q就可以解题，如果Q<L[i-1]第一项消失.如果允许负元素，那么你也需要考虑负 Qs。