<p>This is called a <a href="http://en.wikipedia.org/wiki/Partition_(number_theory)" rel="nofollow noreferrer">partition problem</a> and approaches are discussed <a href="http://home.att.net/~numericana/answer/numbers.htm#partitions" rel="nofollow noreferrer">here</a>, <a href="http://www.site.uottawa.ca/~ivan/F49-int-part.pdf" rel="nofollow noreferrer">here</a> and <a href="http://arxiv.org/PS_cache/arxiv/pdf/0909/0909.2331v1.pdf" rel="nofollow noreferrer">here</a>.</p>
Generate all of the unique combinations of numbers that add up to a certain number
<p>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:</p>

<pre><code>5 0 0 0
4 1 0 0 
3 2 0 0
3 1 1 0
2 2 1 0
2 1 1 1
</code></pre>

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

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

<p>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 <strong>maximum N of about 25</strong>.  Do you guys have any ideas?  </p>

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

<pre><code>// 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&gt;=0; a--) {
    row[0] = a;

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

      for (int c=target-(a+b); c&gt;=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]);
      }
    }
  }
}
</code></pre>