查找数组中添加到输入数字的所有数字组合
嘿，我正在研究一种算法，该算法采用用户输入的数字，然后通过一个大小为50的数组填充1到100之间的随机数，并查找加起来输入数字的所有数字组合。
例如，给定一个整数数组[3,6,1,9,2,5,12]并传递整数值9，你将返回[[3,6]，[6,1,2]，[ 9]，[3,1,5]。 在数组中返回结果的顺序无关紧要，尽管你应该返回唯一的集合（即[6,3]和[3,6]是相同的，只返回一个）。 此外，个别结果应该按照它们的顺序排列（即[6,1,2]应该返回，而不是[1,2,6]）。
当我开始编写代码时，我遇到的第一个解决方案看起来非常低效。 我目前正在尝试将每个组合分成它自己的数组，并且每次将一个数字添加到数组时，都会检查数字是否等于输入，是否仍然小于或超过它。 它工作不正常，我觉得这可能是一种效率低下的方法：
for (int i = 0; i < list.length; i++) { List combo = new ArrayList(); int counter = 0; int current = list[i]; if (current == input){ System.out.println(i); } else if (current > input) { continue; } else if (current = 2) { for (int j = 0; j < combo.size(); j++) { counter += combo.get(j); if (counter == input) { System.out.println("Success"); break; } else if (counter input) { break; } } } } } 这是一个想法，我没有工作代码。 尝试使用递归，测试具有最大可能数量的所有组合以及没有它的所有其余组合。 function如：Sums（Number，maxN），（maxN是我们可以采用的最大数量 – 首先调用它为9）对于您的示例将是：
1.按照建议，对它们进行排序并切割大于输入。
2.检查maxN是否大于总和所需的最小值，在你的例子中它是5（在你的集合中不能从小于5的数字中取9）; 如果它没有返回（基本情况）。
3. maxN是否等于输入？ （第一次打电话9）
a）是 – 第一个解决方案子集[9] + Sums（Number，dec（maxN））（dec（maxN）在第一次调用时将为6）
b）否 – 递归检查是否可以根据您的数字中的数字构建’Number – maxN’，Sums（Number – maxN，dec（K）或’Number – maxN’的最大数量（取决于更小））+ Sums（ Number，dec（maxN）） – 添加其余部分。
这里是只计算的代码，将数字写成平方和的方法，它通过了HackerRank测试：
import math def minArgument(x): s = 0 i = 1 while s < x: s = s + i * i i = i + 1 return i - 1 def maxPower(a): return math.floor(math.sqrt(a)) def sumOfSquares(M, K, cnt): if M < 1: return cnt lowerLimit = minArgument(M) if K < lowerLimit: return cnt else: if K * K == M: return sumOfSquares(M, K - 1, cnt + 1) else: return sumOfSquares(M, K - 1,sumOfSquares(M - K * K, min(maxPower(M - K * K), K - 1), cnt))
经过简单的更改后，这将为您提供多种解决方案。 我现在看不到如何使用组合构建一个列表作为返回值...