Print all ways to sum n integers so that they total a given sum.

Question

Im trying to come up with an algorithm that will print out all possible ways to sum N integers so that they total a given value.

Example. Print all ways to sum 4 integers so that they sum up to be 5.

Result should be something like:

5 0 0 0

4 1 0 0

3 2 0 0

3 1 1 0

2 3 0 0

2 2 1 0

2 1 2 0

2 1 1 1

1 4 0 0

1 3 1 0

1 2 2 0

1 2 1 1

1 1 3 0

1 1 2 1

1 1 1 2

Answer 1

I haven't tested this:

  procedure allSum (int tot, int n, int desiredTotal) return int
       if n > 0
           int i = 
           for (int i = tot; i>=0; i--) {
               push i onto stack;
               allSum(tot-i, n-1, desiredTotal);
               pop top of stack
            }
        else if n==0
            if stack sums to desiredTotal then print the stack   end if
        end if

I'm sure there's a better way to do this.

Answer 2

The key to solving the problem is recursion. Here's a working implementation in python. It prints out all possible permutations that sum up to the total. You'll probably want to get rid of the duplicate combinations, possibly by using some Set or hashing mechanism to filter them out.

def sum(n, value):
    arr = [0]*n  # create an array of size n, filled with zeroes
    sumRecursive(n, value, 0, n, arr);

def sumRecursive(n, value, sumSoFar, topLevel, arr):
    if n == 1:
        if sumSoFar > value:
            return False
        else:
            for i in range(value+1): # i = 0...value
                if (sumSoFar + i) == value:
                    arr[(-1*n)] = i # put i in the n_th last index of arr
                    print arr;
                    return True

    else:
        for i in range(value+1): # i = 0...value
            arr[(-1*n)] = i  # put i in the n_th last index of arr
            if sumRecursive(n-1, value, sumSoFar + i, topLevel, arr):
                if (n == topLevel):
                    print "\n"

With some extra effort, this can probably be simplified to get rid of some of the parameters I am passing to the recursive function. As suggested by redcayuga's pseudo code, using a stack, instead of manually managing an array, would be a better idea too.

Answer 3

This is based off Alinium's code.
I modified it so it prints out all the possible combinations, since his already does all the permutations.
Also, I don't think you need the for loop when n=1, because in that case, only one number should cause the sum to equal value.
Various other modifications to get boundary cases to work.

def sum(n, value):
    arr = [0]*n  # create an array of size n, filled with zeroes
    sumRecursive(n, value, 0, n, arr);

def sumRecursive(n, value, sumSoFar, topLevel, arr):
    if n == 1:
        if sumSoFar <= value:
            #Make sure it's in ascending order (or only level)
            if topLevel == 1 or (value - sumSoFar >= arr[-2]):
                arr[(-1)] = value - sumSoFar #put it in the n_th last index of arr
                print arr
    elif n > 0:
        #Make sure it's in ascending order
        start = 0
        if (n != topLevel):
            start = arr[(-1*n)-1]   #the value before this element

        for i in range(start, value+1): # i = start...value
            arr[(-1*n)] = i  # put i in the n_th last index of arr
            sumRecursive(n-1, value, sumSoFar + i, topLevel, arr)

Runing sums(4, 5) returns:
[0, 0, 0, 5]
[0, 0, 1, 4]
[0, 0, 2, 3]
[0, 1, 1, 3]
[1, 1, 1, 2]

Answer 4

In pure math, a way of summing integers to get a given total is called a partition. There is a lot of information around if you google for "integer partition". You are looking for integer partitions where there are a specific number of elements. I'm sure you could take one of the known generating mechanisms and adapt for this extra condition. Wikipedia has a good overview of the topic Partition_(number_theory). Mathematica even has a function to do what you want: IntegerPartitions[5, 4].