Good people of stackoverflow, I am trying to implement an algorithm that for a fixed given array of doubles (i.e. [1.0, 0.5, 0.25] is giving all possible combinations that sum up to for example 1.0. In this case, the output should look like:

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

I tried to achieve this with two nested for-loops and can't figure it out. Any help would be highly appreciated.

This is my shameful attempt so far:

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);
        }
    }
}

Thanks

CodePudding user response：

You can solve this using recursion. Below is my approach with some explanation:

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);
            }
        }
    }
}