c++ - 生成加起来等于某个数字的所有唯一数字组合

Question

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

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 编写此代码，但似乎无法提出令人满意的解决方案。我需要它达到 大约 25 的最大 N。你们有什么想法吗？

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

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

这叫做 partition problem和方法进行了讨论 here , here和 here .