java - 查找具有条件的给定数组的数字集的算法

Question

用户给定一个大小为 N 的整数数组。打印所有可能的集合，使得所有可能数字的总和等于数组中的一个数字。

例子:

数组 A[]= {1,2,3,4,5}

1+2=3..输出:1,2,3

1+3=4..输出:1,3,4

1+4=5..输出:1,4,5

初始设计:

1. 取一个数字并将其设置为 SetSum
2. 生成除所选数字之外的所有总和；检查制定的总和是否与 SetSum 相同
3. 打印出满足上述条件的数字。
4. 遍历数组并将下一个数字设置为 SetSum

欢迎更高效的设计/实现或不同的方法..

Answer 1

此问题要求您找到总和等于给定数字(这里是集合的一个元素)的子集。有两种方法可以做到这一点:

1. 一种蛮力算法，您手动生成所有子集并将它们全部相加，这是指数级增长(2^n 组合)或

2. 使用动态规划方法解决问题并在多项式时间内求和。这是算法中的一个标准问题，称为子集求和问题。如果您不熟悉动态规划的概念，可以查阅任何算法教科书。如果你了解动态规划，那么谷歌搜索子集和问题。希望对您有所帮助!