Check all combinations of numbers for a given sum

[Killer42]

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]

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

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

[r035198x]

Cute integer partitioning that.

[JosAH]

Cute integer partitioning that.

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 ... ;-)

kind regards,

Jos

[Killer42]

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]

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]

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.

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]

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.

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

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]

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

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]

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

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]

...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.