473,890 Members | 2,012 Online

# Check all combinations of numbers for a given sum

8,435 Recognized Expert Expert
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.
Mar 11 '08 #1
10 10785
JosAH
11,448 Recognized Expert MVP
Ok I'll bite; just a bit of resursion will do; here's a solution:

Expand|Select|Wrap|Line Numbers
1. import java.util.ArrayList;
2. import java.util.List;
3.
4. public class Sum {
5.     private static int[] numbers= { 6, 5, 4, 3, 2, 1 };
6.     private static int[] sumsum= new int[numbers.length];
7.
8.     private static int sum= 10;
9.
10.     private static void solution(List<Integer> solution) {
11.
12.         System.out.println(solution);
13.     }
14.
15.     private static void solve(int[] numbers, int i, int sum, List<Integer> solution) {
16.
17.         if (sum == 0)
18.             solution(solution);
19.         else
20.             for (; i < numbers.length && sumsum[i] >= sum; i++) {
21.                 if (numbers[i] <= sum) {
23.                     solve(numbers, i+1, sum-numbers[i], solution);
24.                     solution.remove(0);
25.                 }
26.             }
27.     }
28.
29.     public static void main(String[] args) {
30.
31.         for (int s= 0, i= numbers.length; --i >= 0; ) {
32.             sumsum[i]= numbers[i]+s;
33.             s+= numbers[i];
34.         }
35.         solve(numbers, 0, sum, new ArrayList<Integer>());
36.     }
37. }
The numbers that make up the problem need to be in descending order (see the code).

kind regards,

Jos
Mar 14 '08 #2
r035198x
13,262 MVP
Cute integer partitioning that.
Mar 14 '08 #3
JosAH
11,448 Recognized Expert MVP
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
Mar 18 '08 #4
Killer42
8,435 Recognized Expert Expert
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.
Mar 18 '08 #5
r035198x
13,262 MVP
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.
Mar 19 '08 #6
Killer42
8,435 Recognized Expert Expert
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.
Mar 20 '08 #7
JosAH
11,448 Recognized Expert MVP
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:

Expand|Select|Wrap|Line Numbers
1. import java.io.IOException;
2.
3. public class Sum {
4.     private static int[] numbers= { 6, 5, 4, 3, 2, 1 };
5.     private static int[] solution= new int[numbers.length];
6.     private static int ptr= 0;
7.     private static int[] sumsum= new int[numbers.length];
8.
9.     private static int sum= 10;
10.
11.     private static void solution() {
12.
13.         for (int i= 0; i < ptr; i++)
14.             System.out.print(solution[i]+" ");
15.         System.out.println();
16.     }
17.
18.     private static void solve(int[] numbers, int i, int sum) {
19.
20.         if (sum == 0)
21.             solution();
22.         else
23.             for (; i < numbers.length && sumsum[i] >= sum; i++) {
24.                 if (numbers[i] <= sum) {
25.                     solution[ptr++]= numbers[i];
26.                     solve(numbers, i+1, sum-numbers[i]);
27.                     ptr--;
28.                 }
29.             }
30.     }
31.
32.     public static void main(String[] args) throws IOException {
33.
34.         for (int s= 0, i= numbers.length; --i >= 0; ) {
35.             sumsum[i]= numbers[i]+s;
36.             s+= numbers[i];
37.         }
38.         solve(numbers, 0, sum);
39.     }
40. }
kind regards,

Jos
Mar 20 '08 #8
Killer42
8,435 Recognized Expert Expert
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
1. solution(ptr) = numbers(x)
2. ptr = ptr + 1
Correct? And if the "ptr++" had been "++ptr" then the increment would have to be done before the assignment?
Mar 25 '08 #9
JosAH
11,448 Recognized Expert MVP
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
1. solution(ptr) = numbers(x)
2. 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
Mar 25 '08 #10