Check all combinations of numbers for a given sum

We have received what looks to me like quite an interesting question in the Visual Basic forum concerning how to check all possible combinations of numbers in a list for those where the sum matches a given number. (That's if I'm explaining it correctly.)

Any mathematicians care to have a look?

If we can come up with an algorithm I expect translating it to VB will be easy enough.

JosAH

Chief Editor

7,734 Posts

March 14th, 2008
09:51 AM
#2

Re: Check all combinations of numbers for a given sum

Ok I'll bite; just a bit of resursion will do; here's a solution:

Expand|Select|Wrap|Line Numbers

	
import java.util.ArrayList;

import java.util.List;
 
public class Sum {

    private static int[] numbers= { 6, 5, 4, 3, 2, 1 };

    private static int[] sumsum= new int[numbers.length];
 
    private static int sum= 10;
 
    private static void solution(List<Integer> solution) {
 
        System.out.println(solution);

    }
 
    private static void solve(int[] numbers, int i, int sum, List<Integer> solution) {
 
        if (sum == 0) 

            solution(solution);

        else

            for (; i < numbers.length && sumsum[i] >= sum; i++) {

                if (numbers[i] <= sum) {

                    solution.add(0, numbers[i]);

                    solve(numbers, i+1, sum-numbers[i], solution);

                    solution.remove(0);

                }

            }

    }
 
    public static void main(String[] args) {
 
        for (int s= 0, i= numbers.length; --i >= 0; ) {

            sumsum[i]= numbers[i]+s;

            s+= numbers[i];

        }

        solve(numbers, 0, sum, new ArrayList<Integer>());

    }

}

The numbers that make up the problem need to be in descending order (see the code).

kind regards,

Jos

Killer42

Site Moderator

7,748 Posts

March 18th, 2008
10:40 PM
#5

Re: Check all combinations of numbers for a given sum

Quote:

Yep, but I guess the answer isn't as interesting as the question was; no replies
nor any interest from the Basic droids; oh well ... ;-)

Probably because the solution is written in gibberish.

Oh, sorry. They call that "Java" these days. ;)

Guess we'll have to mount a translation project.

r035198x

Administrator

10,738 Posts

March 19th, 2008
06:42 AM
#6

Re: Check all combinations of numbers for a given sum

Quote:

Probably because the solution is written in gibberish.

Oh, sorry. They call that "Java" these days. ;)

Guess we'll have to mount a translation project.

I can translate that to C# if you want ... not that it will look much different but it's the only .NET language I can write code in without feeling ashamed of myself.
Just look at it as pseudo code and pick up the recursion used for the generating function.

Killer42

Site Moderator

7,748 Posts

March 20th, 2008
02:12 AM
#7

Re: Check all combinations of numbers for a given sum

Quote:

Yeah, I think the overall structure with the recursion is simple enough to understand. It's the specifics of what certain statements or references mean that stopped me when I glanced over it. Will have a proper look over the long weekend and see if it makes any more sense.

JosAH

Chief Editor

7,734 Posts

March 20th, 2008
03:38 PM
#8

Re: Check all combinations of numbers for a given sum

Quote:

I'll make it easier for you and mutilate the previous algorithm implementation:

Expand|Select|Wrap|Line Numbers

	
import java.io.IOException;
 
public class Sum {

    private static int[] numbers= { 6, 5, 4, 3, 2, 1 };

    private static int[] solution= new int[numbers.length];

    private static int ptr= 0;

    private static int[] sumsum= new int[numbers.length];
 
    private static int sum= 10;
 
    private static void solution() {
 
        for (int i= 0; i < ptr; i++)

            System.out.print(solution[i]+" ");

        System.out.println();

    }
 
    private static void solve(int[] numbers, int i, int sum) {
 
        if (sum == 0)

            solution();

        else

            for (; i < numbers.length && sumsum[i] >= sum; i++) {

                if (numbers[i] <= sum) {

                    solution[ptr++]= numbers[i];

                    solve(numbers, i+1, sum-numbers[i]);

                    ptr--;

                }

            }

    }
 
    public static void main(String[] args) throws IOException {
 
        for (int s= 0, i= numbers.length; --i >= 0; ) {

            sumsum[i]= numbers[i]+s;

            s+= numbers[i];

        }

        solve(numbers, 0, sum);

    }

}

kind regards,

Jos

Killer42

Site Moderator

7,748 Posts

March 25th, 2008
02:27 AM
#9

Re: Check all combinations of numbers for a given sum

Quote:

I'll make it easier for you and mutilate the previous algorithm implementation ...

Thanks. Ended up being too busy over the long weekend. Will try to get into it this week.

I really hate the two-in-one features of Java, though. You know, things like... solution[ptr++]= numbers[x]; - I believe this would translate as something like

Expand|Select|Wrap|Line Numbers

	
solution(ptr) = numbers(x)

ptr = ptr + 1

Correct? And if the "ptr++" had been "++ptr" then the increment would have to be done before the assignment?

JosAH

Chief Editor

7,734 Posts

March 25th, 2008
07:32 AM
#10

Re: Check all combinations of numbers for a given sum

Quote:

Expand|Select|Wrap|Line Numbers

	
solution(ptr) = numbers(x)

ptr = ptr + 1

Correct? And if the "ptr++" had been "++ptr" then the increment would have to be done before the assignment?

Yep, correct; it isn't a Java invention. In the dark ages CPL already implemented
those pre- and post-increments. BCPL inherited them and later along the path
B, C, C++ and Java implemented those operators as well. The operators are
directly inspired by the 'inc' machine code instructions that were/are available
on many processors and are quite handy when you get used to them.

kind regards,

Jos

Killer42

Site Moderator

7,748 Posts

March 26th, 2008
04:48 AM
#11

Re: Check all combinations of numbers for a given sum

Quote:

...quite handy when you get used to them.

Oh yes, I can see how they'd allow much more compact code. It just seems as though it comes at too high a cost in readability.

Perhaps I simply need more experience.