find all combinations of elements for the given number N (sum upto N)

Question

int array [] = {1,2,3,4,5,6,7,8,9}
N = 10

1,2,3,4 = 10
2,3,5 = 10
3,7 = 10
1,4,5 = 10
1,3,6 = 10
8,2 = 10
9,1 = 10
4,6 = 10
5,2,3 = 10
...

the function should return all combinations, the array may be unsorted

Answer 1

This is part of the number theory, and is called "Composition". This wikipedia article has the theoretical information and links to a site where you can find Java code samples.

Answer 2

Your examples give a hint.

• Check all sums of one integer for a match
• Check all sums of two integers for a match
• Check all sums of three integers for a match
• . . .

When do you stop checking?

Answer 3

Here's a nice and simple way of doing it. First of all, the time complexity of any algorithm that lists all combinations is going to be O(N*2^N) since you have to check each subset. So if you want your algorithm to ever finish, it's safe to assume that N won't be much larger than ~25.

We can use a single 32 bit unsigned integer to solve this. Count from 1 to 2^N in an integer i, then for each value of i, check all of its bits. If the k-th bit is 1, add array[k] to the sum. Check if the sum equals your required sum, and if yes, print the positions of the 1-bits.

Pseudo-C code:

int sum = 0;
cin >> requiredSum;
// assume array = your array of numbers and N = size of array
for ( unsigned int i = 1; i < (1 << N); ++i, sum = 0 )
{
    for ( unsigned int k = 0; k < 32; ++k )
        if ( (i & (1 << k)) != 0 )
            sum += array[k];

    if ( sum == requiredSum )
    {
        for ( unsigned int k = 0; k < 32; ++k )
            if ( (i & (1 << k)) != 0 )
                cout << array[k] << ' '; 
        cout << endl;
    }
}

Formulas i've used:

1 << N == 2 to the power of N

i & (1 << k) != 0 if the k-th bit of i is 1 and 0 otherwise.

You can read more about bitwise operations here.

This is a lot more elegant than recursion is, and probably faster. If your array can have more than 32 elements, then this won't work, however it's unlikely that it can, as that would take way too much time to list the solutions. Counting them would be possible though. Anyway, there are also 64 bit integers...