Add numbers of array until certain value

This seems to be solvable easily with recursion, like this :

Getting the solution for 4 and {1,2,3} (written below as solution(4, {1,2,3}) is like getting the solution for

• "1 + " + solution(3, {1, 2, 3})
• "2 + " + solution(2, {1, 2, 3})
• "3 + " + solution(1, {1, 2, 3})

At each step, you decrease the number (if there is not 0 in the list of available numbers, of course), so you are sure that the recursion will finish.

You can have two outcome :

• no possibility (like you need to produce 1, but there is not 1 in the list of available numbers)
• 1 or more potential solutions

There is another thing to pay attention to : floating point equality. == will not work everytime.

the code would like like :

public static void main(String[] args) {
    ArrayList<String> solutions = new ArrayList<String>();
    solve("", 1.0d, new Double[] {0.2d, 0.50d}, solutions);
    System.out.println(solutions);
    // [0.2 + 0.2 + 0.2 + 0.2 + 0.2, 0.5 + 0.5]
    solutions.clear();
    solve("", 4d, new Double[] {1d, 2d, 3d}, solutions);
    System.out.println(solutions);
    // [1.0 + 1.0 + 1.0 + 1.0, 1.0 + 1.0 + 2.0, 1.0 + 2.0 + 1.0, 1.0 + 3.0, 2.0 + 1.0 + 1.0, 2.0 + 2.0, 3.0 + 1.0]
}

public static void solve(String subSolution, Double remaining, Double[] authorizedNumbers, List<String> solutions) {
    if (doubleEquals(remaining, 0d)) {
        solutions.add(subSolution);
    } else {
        for(Double authorizedNumber : authorizedNumbers) {
            if (doubleEquals(authorizedNumber, remaining)) {
                solutions.add(subSolution + authorizedNumber);
            } else if (authorizedNumber < remaining) {
                solve(subSolution + authorizedNumber + " + ", remaining - authorizedNumber, authorizedNumbers, solutions);
            }
        }
    }
}

public static boolean doubleEquals(double d1, double d2) {
    return Math.abs(d1 - d2) < 0.000000001d;
}

Here is one of the solutions based on Combination Technique.

Algorithm:

1. Compute all the combination (with repetition) from length {input} to 1.
2. Print only those combinations which satisfy the sum condition.

For Example, if input is 4 then some of the different combinations of length = 4 will be as follows:

1 1 1 1
1 1 1 2
.
.
2 1 2 3
.
.
3 3 3 3

Now, we'll only print 1 1 1 1 since it sums up to input i.e. 4 and satisfies the condition.

Similarly, for length = 3 some of the different combinations will be as follows:

1 1 1
1 1 2
.
.
1 2 1
.
.
3 3 3

Now, we'll only print 1 1 2, 1 2 1 and 2 1 1 since they all satisfy the sum condition.

Here is a brief description of how different combinations are computed:

1. Combination function checks for the last element of the array and increments it if it is not MAX and branches the function.
2. If the last element is max then we scan through the array for next number that is not MAX.
3. If the above scan fails as the array is exhausted then we return the flow to our main function but, if the scan return a position which is not max then we increment the value at that position by 1 and reset all the values after that position to MIN. We again branches the function.

(It computes all the combinations for a given length using recursion)

Code Snippet:

class Combinations
{
    /* Constants Array (Sorted) */
    private static final double[] ARR_CNST = {0.1,0.2,0.3};
    /* Size of Constant Array */
    private static final int SIZE = 3;

    public static void main (String[] args)
    {
        /* Input Number */
        double input = 0.4;
        /* Start Permutations {Length --> 1} */
        for(int i = (int) (input/ARR_CNST[0]); i > 0; i--) {
            double[] storage = new double[i];
            /* Fill Array With Least Element */
            Arrays.fill(storage,ARR_CNST[0]);
            /* Check Sum Condition */
            if(check(storage,input)) {
                /* Print */
                print(storage);
            }
            /* Calculate Rest of the Combinations */
            calc(storage, input);
        }
    }

    private static void calc(double[] arr, double input) {
        /* Increment Last Element if not MAX */
        if(arr[arr.length - 1] < ARR_CNST[SIZE - 1]) {
            int k = 0;
            while(k < SIZE && arr[arr.length - 1] != ARR_CNST[k++]);
            arr[arr.length - 1] = ARR_CNST[k];
            if(check(arr,input)) {
                print(arr);
            }
            calc(arr, input);
        }

        /* Increment & Reset */
        int i = arr.length - 1;
        while(i >= 0 && arr[i] >= ARR_CNST[SIZE - 1])
            i--;

        if(i >= 0) {
            int k = 0;
            while(k < SIZE && arr[i] != ARR_CNST[k++]);
            arr[i] = ARR_CNST[k];

            for(int x = i + 1; x < arr.length; x++) {
                arr[x] = ARR_CNST[0];
            }

            if(check(arr,input)) {
                print(arr);
            }
            calc(arr, input);
        }

        /* Return */
        return;
    }

    /* Check Sum Condition */
    private static boolean check(double[] arr, double input) {
        double sum = 0;
        for(int i = 0; i < arr.length; i++) {
            sum += arr[i];
        }
        if(sum == input) {
            return true;
        }
        return false;
    }

    /* Print Array Values */
    private static void print(double[] arr) {
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < arr.length; i++) {
            sb.append(arr[i] + " + ");
        }
        System.out.println(sb.substring(0,sb.length() - 3));
    }
}

Output:

0.1 + 0.1 + 0.1 + 0.1
0.1 + 0.1 + 0.2
0.1 + 0.2 + 0.1
0.2 + 0.1 + 0.1
0.1 + 0.3
0.2 + 0.2
0.3 + 0.1