java - java-使用递归查找子集和

Question

该程序的目标是查看数组中的一个输入是否可以是其他输入的任意组合的总和。我了解它背后的理论，并想出了如何解决它，但我不确定如何实现它。我决定将数组从最小到最大排序，然后我想我会先将数字对与以下输入进行比较，然后使用 3 个输入，然后是 4 个，等等，但我不知道如何使用递归来解决这个问题。一些方向将非常有帮助，而不是寻找完整的答案谢谢！

Answer 1

让我看看..

你需要一个目标总和，这就是争论之一。

到目前为止，您需要一笔总和，所以那是另一笔。

Boolean IsSubsetSum(int[] sorted array, int Target,int maxIndex , int SumSoFar = 0);

这听起来是个不错的起点。

如果 SumSoFar == 目标

返回真

否则如果 maxIndex == 0

返回假

别的

将 array[maxIndex] 添加到总和并使用适当的参数递归调用..

此步骤将循环 0..maxIndex，因此效率不高，但可以作为开始。您需要根据recusive调用的返回值计算返回值，如果您发现为真，您可以提前退出。