Generate all of the unique combinations of numbers that add up to a certain number.

Question

Hi Everyone,

I am writing a program to try to solve a math problem. I need to generate a unique list of all of the numbers that add up to another number. For example, all of the unqiue combinations of 4 numbers that add up to 5 are:

5 0 0 0
4 1 0 0 
3 2 0 0
3 1 1 0
2 2 1 0
2 1 1 1

This is easy to brute force in perl but I am working in C and would like to find a more elegant solution.

In perl I would generate every possible combination of numbers 0-N in each column, discard the ones that don't add up to the target number, then sort the numbers in each row and remove the duplicate rows.

I've been trying all morning to write this in C but can't seem to come up with a satisfactory solution. I need it to work up to a maximum N of about 25. Do you guys have any ideas?

Here is an example of the kind of thing I have been trying (this produces duplicate combinations):

// target is the number each row should sum to.
// Don't worry about overflows, I am only using small values for target
void example(int target)
{

  int row[4];

  for (int a=target; a>=0; a--) {
    row[0] = a;

    for (int b=target-a; b>=0; b--) {
      row[1] = b;

      for (int c=target-(a+b); c>=0; c--) {
        row[2] = c;

        row[3] = target-(a+b+c);

        printf ("%2d %2d %2d %2d   sum: %d\n", row[0],row[1],row[2],row[3],
                                          row[0]+row[1]+row[2]+row[3]);
      }
    }
  }
}

Answer 1

This is called a partition problem and approaches are discussed here, here and here.

Answer 2

With the numbers being no larger than 25, a recursive solution might be okay. Pseudocode:

function get_summand_list(number)
{
    if number == 0: return empty list

    for first from number downto 1
    {
        combination = [first_number] + get_summand_list(number - first)
    }
    return all combinations
}

Answer 3

If the number of columns is fixed, the easiest way is let the numbers non-decreasing.

void example(int target) {
  for (int a=0;a<=target;a++)
    for (int b=a;b<=target-a;b++)
      for (int c=b;c<=target-(a+b);c++) {
        int d = target-(a+b+c);
        if(d>=c) printf ("%2d %2d %2d %2d\n",d,c,b,a);
      }
}

Recursive search is preferred for more general situation. But anyway, the bottleneck of this problem is output, not counting.

Answer 4

Notice you don't want any b>a or any c>b. You can say that in your program

for (b ...) {
    if (b > a) continue; /* continue bypasses the following code and
                          * return control to the loop */
    /* ... */
}

Also, you don't want any negative row[3].

Answer 5

Generate the lists in sorted order and you don't have to worry about removing duplicates.

Hint: a = (target .. 0), b = (a .. 0), c = (b .. 0), d = (c .. 0)

Answer 6

To solve this problem efficiently (modulo the fact it is an exponential problem) you want to search the space, in a way that is non-redundant, and prunes impossible solutions, or partial solutions that cannot lead to a possible solution, as soon as possible.

The easiest way is to do this wth a recursive procedure. Note as mentioned by the poster above, you can always generate the list in sorted order, to avoid generating duplicates. So, your choices must always be greater (or less than) the last element chosen.

Also, the sum of the x min elements remaining to be chosen, added to the current total, must be less than your target value. I.e. if you've chosen numbers that add up to 20, and you have to choose 3 more elements, and you have to make it add up to 25, and the only choices are 1, 2, and 3, then you won't be able to complete the list (it will add up to 26) so you can prune that soluion.

So, in your recursive solution,

1. check to see if you are on the way to a feasible solution. If not, simply exit the function.

2. if you have completed a list, and it adds up to your target, print out the list and exit.

3. for each of the valid remaining choices, append it to your current solution, and call function recusively with current solution and current choices list. (you have to remove that choices for the next iteration of the for loop).

That should generate it.

I've written this type of code many times before, so it would be easy for me to post a solution, but I gather this is homework so I'm not going to do that. The above is fairly complete description of the solution, however. The trick to making it simple is to use a recursive solution - non-recursive solutions will be very messy as you will need to basically simulate recursion using a stack etc to get an efficient solution.