Add numbers of array until certain value

Question

For an exercise, I have to add values of an array until a certain value is reached, showing all possible combinations.

Example: value = 4, array = {1, 2, 3}

Possible combinations are: 1+1+1+1, 1+1+2, 1+2+1, 1+3, 2+1+1, 2+2, 3+1

However, my code doesn't seem to work:

public static void main(String[] args) {

    double[] array = { 1., 2., 3. };
    double value = 4.;
    for (int i = 0; i < array.length; i++) {
        addNumber(array, value, i);
    }
}

public static void addNumber(double[] array, double value, int index) {

    double startNumber = array[index];
    double checkSum = 0;

    for (int i = 0; i < array.length; i++) {
        checkSum += array[i] + startNumber;
        if (checkSum == value){
        System.out.println(startNumber + " + " + array[i] + " = " + checkSum);
        } else if (checkSum < value){
            moreNumbers(array, value, checkSum);
        }
        checkSum = 0;
    }
}

public static void moreNumbers (double[] array, double value, double current){

    if (current == value){
        System.out.println(current);
    } else if (current < value) {

        for (int i = 0; i < array.length; i++){             
            current += array[i];
            System.out.println("+ " + array[i] + " = " + current);              
        }
        moreNumbers(array, value, current);
    }       
}

Output:

+ 1.0 = 3.0
+ 2.0 = 5.0
+ 3.0 = 8.0
+ 1.0 = 4.0
+ 2.0 = 6.0
+ 3.0 = 9.0
1.0 + 3.0 = 4.0
+ 1.0 = 4.0
+ 2.0 = 6.0
+ 3.0 = 9.0
2.0 + 2.0 = 4.0
3.0 + 1.0 = 4.0

I believe I'm having trouble finding the right algorithm, since I'm only getting some of the combinations, but not all.

And there is my question: I'm looking for an algorithm that helps me understand this exercise and it's logic, not the final code.

EDIT: In further development of this exercise, I have to use numbers like 0.5 or 0.2 too, but the numbers are always positive, so this is another problem I'm hoping to find answers for.

Answer 1

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

Answer 2

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

Answer 3

The general approach is:

1. Pick one of the available numbers, and see if that equals the target.
2. If not, you can pick any other number from the available numbers and add it to the previously picked number; again, check if you have reached the target.
3. Keep going until you have reached (or gone past) the target sum.

This can be implemented like this:

public static void startRecursion(int target, int[] numbers) {
  int min = numbers[0];
  for (int i = 1; i < numbers.length; ++i) {
    min = Math.min(min, numbers[i]);
  }
  // We need to choose at most ceil(target / min) numbers.
  int maxPicks = (target + min - 1) / min;
  recurse(new int[maxPicks], 0, 0, target, numbers);
}

private static void recurse(
    int[] picked, int numPicked, int sumOfPicked,
    int target, int[] numbers) {
  if (sumOfPicked == target) {
    // We reached the target! Print out the numbers we chose to get here.
    for (int i = 0; i < numPicked; ++i) {
      if (i != 0) System.out.print(" + ");
      System.out.print(picked[i]);
    }
    System.out.println(" = " + target);
  } else if (sumOfPicked < target) {
    // We haven't reached the target yet.
    // Go through each of the numbers that you can choose from numbers
    // in turn, increasing the sum by this amount.
    for (int i = 0; i < numbers.length; ++i) {
      picked[numPicked] = numbers[i];
      recurse(
          picked, numPicked + 1, sumOfPicked + numbers[i],
          target, numbers);
    }
  } else {
    // We have overshot the target. Since no numbers are negative,
    // we can't get back to the target again.
  }
}