How to calculate a summation of an arbitrary set of numbers, and all subsets of those numbers?

Question

Say that I have a set of numbers:

Group1 = 10, Group2 = 15, Group3 = 20, Group4 = 30

I want to output the summation of all subsets of numbers

10 + 15 = 25
10 + 15 + 20 = 45
10 + 15 + 20 + 30 = 75
15 + 20 = 35
15 + 20 + 30 = 65
20 + 30 = 50
10 + 20 = 30
10 + 30 = 40
10 + 20 + 30 = 60
... (assumed the rest is typed out)

Each of these groups will have a name, so I would want to print out the names used in the calculation before the result:

Group1 + Group2 = 25

How to do such a thing?

EDIT: to JacobM who edited tags, this is NOT homework and would appreciate an ask before you start editing it as such. I am actually at a customer site who is trying to balance a set of numbers, and the result is coming up incorrectly. My thought was to identify which group of numbers is equal to the delta between the 2 sets, and that would identify the problem directly.

Note: this would be float values, not integers.

EDIT2: added arbitrary so that it is understood that I can not just type this out once with a bunch of string.format's .. I could easily use excel at that point.

Answer 1

My thought was to identify which group of numbers is equal to the delta between the 2 sets, and that would identify the problem directly.

The problem "given an integer s, and a set of integers, does any non-empty subset of the set sum to s?" is known as the "subset sum problem". It is extremely well studied, and it is NP-Complete. (See this link for a related problem.)

That is to say it is amongst the hardest problems to solve in a reasonable amount of time. It is widely believed (though at present not proved) that no polynomial-time algorithm can possibly exist for this problem. The best you can do is something like O(2^n) for a set containing n elements.

(I note that your problem is in floats, not integers. It doesn't really matter, as long as you correctly handle the comparison of the calculated sum to the target sum to handle any rounding error that might have accrued in doing the sum.)

For a small number of elements -- you say you have only 15 or so in the set -- your best bet is to just try them all exhaustively. Here's how you do that.

The trick is to realize that there is one subset for each integer from 0 to 2^n. If you look at those numbers in binary:

0000
0001
0010
0011
...

each one corresponds to a subset. The first has no members. The second has just group 1. The third has just group 2. The fourth has group 1 and group 2. And so on.

The pseudocode is easy enough:

for each integer i from 1 to 2^n
{
  sum = 0;
  for each integer b from 1 to n
  {
    if the bth bit of i is on then sum = sum + group(b)
  }
  if sum == target then print out i in binary and quit
}
quit with no solution

Obviously this is O(n 2^n). If you can find an algorithm that always does better than O(c^n), or prove that you cannot find such an algorithm then you'll be famous forever.

The Wikipedia article has a better algorithm that gives an answer much faster most but not all of the time. I would go with the naive algorithm first since it will only take you a few minutes to code up; if it is unacceptably slow then go for the faster, more complex algorithm.