Java中求和等于2的二重数组的所有组合的算法

Question

我正在尝试实现一种算法，对于一个固定的给定双数组(即[1.0，0.5，0.25](，它给出了所有可能的组合，例如1.0。在这种情况下，输出应该看起来像：

1.0
0.5 0.5
0.5 0.25 0.25
0.25 0.25 0.25 0.25
0.25 0.25 0.5
0.25 0.5 0.25

我试图通过两个嵌套的for循环来实现这一点，但无法实现。如有任何帮助，我们将不胜感激。

这是我迄今为止的尝试：

private double[] a = {1, 0.5, 0.25};
private double max = 1;
private String as;
private double help;
private boolean done;
public void comb()
{
for (var i = 0; i < a.length; i++)
{
for (var j = 0; j < a.length; j++)
{
as ="";
help = 0;
while (help < max)
{
if(help + a[i] <= max)
{
as += a[i] + " ";
help += a[i];
}
/*else if (help + a[j] <= max)
{
ausdruck += a[j] + " ";
help += a[j];
}*/
}
System.out.println(as);
}
}
}

Answer 1

您可以使用递归来解决此问题。以下是我的方法和一些解释：

public class Main {
public static void main(String[] args) {
double[] a = {1, 0.5, 0.25};
double max = 1;
//pass the array, target value and an empty list to the method
comb(a, max, new ArrayList<>());
}
public static void comb(double[] a, double max, List<Double> scores) {
//sum the numbers included in the list
double scoresSum = scores.stream().reduce(0.0, Double::sum);
//print the list if the sum of numbers in the list equals target value
if (scoresSum == max) {
System.out.println(scores);
} else if (scoresSum > max) {
//stop the method if the sum of numbers in the list is larger than the target value
} else {
//if the sum of numbers in the list is smaller than the target value, for each value from the array:
//- create copy of the list
//- add the value
//- run the method passing the updated list as an argument
for (double v : a) {
List<Double> scoresPlusOne = new ArrayList<>(scores);
scoresPlusOne.add(v);
comb(a, max, scoresPlusOne);
}
}
}
}