给定整数集的子集，其和为常数N:Java

Question

给定一组整数，如何找到与给定值求和的子集。。。子集问题？

示例：S={1,2,4,3,2,5}和n=7求和为n的可能子集。我试着在谷歌上找到了很多链接，但都不清楚。我们如何在java中解决这个问题，要使用的数据结构是什么及其复杂性？

Answer 1

分三步：

1. 求S的幂集（S的所有子集的集）

2. 计算每个子集的总和

3. 筛选出总和不为7的子集。

Answer 2

我不会给你任何代码，但会解释它是如何工作的。

1. 从0 to (2^k-1)运行循环
2. 对于1中的每个值，二进制表示中的1表示选择了该值，否则为0
3. 测试所选数字的总和是否等于n

上述方法将评估给定集合的每个可能子集。

如果数值的上限很小，那么可以使用动态规划方法。