Efficient way of generating all possible sums of N out of given numbers

Question

I was thinking about an algorithm to this problem:

Imagine we have the following array

a = {1, 2, 4, 5, 7}

and want to get all possible sums out of these numbers that are equal to a given number N (The order of the summands isn't interesting for now).

In case of N=8 a few valid answers are:

1+2+5
1+7
2+2+2+2
...

So now I will explain you my approach.

First of all we make a new array b of the length N+1 and put every number x from array a to the array b at index [N-x] and fill the remaining elements with -1.
This should create the following array:

b = {-1, 7, -1, 5, 4, -1, 2, 1, -1}

As you can see every element of b that is not -1 needs to be added to its index to get N. (Example: b[1]=7 => Index = 1, value = 7 => 7+1=8=N)

What we do now is, we go through every index x of this array where b[x]!=-1 and start the whole process from the beginning but this time we say N=x so that we get all possible sums to get the index x which (as shown above) is the value we need to add to the value of the element at b[x].

We do all of this recursively and as soon as we get to a point where an index is equal to 0, we print the whole chain of summands.

I implemented this in Java and it works fine:

public static void main(String[] args) {
        int[]numbers = {1, 2, 4, 5, 7};
        int n = 8;
        
        numbers = summandArray(numbers, n);
        printArray(numbers);
        
        
        getSums(numbers, n, "");
        
    }
    
    public static void getSums(int[] numbers, int n, String summands) {
        String startSummands = summands;
        for(int i = 0; i < numbers.length; i++) {
            summands = startSummands;
            if(numbers[i] != -1) {
                int neededSummand = i;
                if(neededSummand == 0) {
                    summands+=numbers[i];
                    System.out.println(summands);
                }
                else {
                    int[] newNumbers = summandArray(numbers, neededSummand);
                    summands+=numbers[i]+"+";
                    getSums(newNumbers, neededSummand, summands);
                }
            }

        }
        
    }
    
    public static int[] summandArray(int[] array, int n) {
        int[] result = new int[n+1];
        for(int i = 0; i < result.length; i++) {
            result[i] = -1;
        }
        for(int i = 0; i < array.length; i++) {
            if(array[i] <= n && array[i] != -1) {
                int index = n-array[i];
                result[index] = array[i];
            }
        }
        return result;
    }

However I am not too sure about how well the algorithm performs. I mean isn't this nothing else than a really complicated version of brute force and thus really inefficient?

Thanks for taking the time

Answer 1

What you are trying to do is get permutations of an array. Using each permutation, you can then total the values if desired. There is another StackExchange hosted site that allows code review to be done. You may want to compare against other's algorithms:

Permutation of array

Print out all permutations of an Array

Answer 2

Your approach starts like effective dynamic-programming algorithm for subset-sum problem (your task is kind of this problem) but seems it does not reuse calculated data. Note that counting the number of possible variants using DP takes pseudo-polynomial time O(N*Sum), while output of all variants grows exponentially.

You can store already calculated subtasks in additional array/list - this is memoization (up-to-down) approach, it is easy to modify recursion to exploit it.

Another DP approach - bottom-up table filling:

 Make array Sol[n+1] of lists of lists
 For every input item X:
      Scan Sol array from the last to the first index i
         if (i==X) or (Sol[i-X] is not empty): 
               Add all Sol[i-X][j]+X to  Sol[X] list

  example for [1,2,3,5] array after outer loops:
  [] [1] []...
  [] [[1]] [[2]] [[1,2]]...
  [] [[1]] [[2]] [[1,2],[3]] [[1,3]] [[2,3]] [[1,2,3]]
  [] [[1]] [[2]] [[1,2],[3]] [[1,3]] [[2,3],[5]] [[1,2,3],[1,5]] 
       [[2,5]] [[1,2,5],[3,5]] [[1,3,5]] [[2,3,5]] [[1,2,3,5]]