小编典典

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

java

给定一组整数,如何找到一个总和为给定值的子集…子集问题?

示例:S = {1,2,4,3,2,5}并且n =
7求和为n的可能子集。我试图用Google搜索出很多链接,但不清楚。我们如何在Java中解决这个问题?要使用什么数据结构及其复杂性?


阅读 242

收藏
2020-11-30

共1个答案

小编典典

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

  1. 从运行循环 0 to (2^k-1)
  2. 对于1中的每个值,其二进制表示中的1表示已选择此值,否则为0。
  3. 测试以查看所选数字的总和是否等于 n

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

如果值的上限较小,则可以使用动态编程方法。

2020-11-30