生成添加到特定数字的所有唯一数字组合

Question

我正在编写一个程序来尝试解决数学问题.我需要生成一个唯一的列表,其中包含与另一个数字相加的所有数字.例如,加起来为5的4个数字的所有unqiue组合是:

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

这在perl中很容易暴力,但我在C中工作并希望找到更优雅的解决方案.

在perl中,我会在每列中生成数字0-N的每种可能组合,丢弃那些不添加到目标数字的组合,然后对每行中的数字进行排序并删除重复的行.

我整个上午都在尝试用C写这个,但似乎无法找到一个令人满意的解决方案.我需要它才能达到最大N约25.你们有什么想法吗？

这是我一直在尝试的一种例子(这会产生重复的组合):

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

这就是所谓的分区的问题和方式进行了讨论这里,这里和这里.