递归函数计数并打印1到n-1的分区

我正在尝试编写一个递归函数（它必须是递归的）来打印 1 到 n-1 的分区和分区数量。 例如，4 个组合的总和为 4：

1 1 1 1
1 1 2
1 3
2 2

我只是在使用该功能时遇到了很多麻烦。下面这个功能不起作用。有人能帮助我吗？

 int partition(int n, int max)
{

  if(n==1||max==1)
    return(1);
  int counter = 0;
  if(n<=max)
    counter=1;
  for(int i = 0; n>i; i++){
          n=n-1;
          cout << n << "+"<< i <<"\n";
          counter++;
          partition(n,i);         
        }

  return(counter);
}

这是解决您的问题的一个好的开始：

#include <stdlib.h>
#include <stdio.h>

void partition(int n, int sum, int *summands, int num_summands)
{
  int i;

  if (sum == n)  // base case of recursion
  {
    if (num_summands > 1)  // don't print n by itself
    {
      for (i = 0; i < num_summands; ++i)
        printf("%d ", summands[i]);

      printf("\n");
    }
  }
  else
  {
    /* TODO: fill in recursive case */
    /* Iteratively recurse after appending one additional, varying summand to summands */
    /* It might be easier to first generate all permutations of the sums */
    /* and then figure out how to reduce that down to only the unique sets of summands (think sorting) */
  }
}

int main(int argc, char **argv)
{
  if (argc == 1)
  {
    printf("usage: %s <num>; where num > 1\n", argv[0]);
    return 1;
  }

  int n = atoi(argv[1]);

  if (n <= 1)
  {
    printf("usage: %s <num>; where num > 1\n", argv[0]);
    return 1;
  }

  int summands[n+1];               // NOTE: +1's are to make summands[-1] always safe inside recursion

  summands[0] = 1;                 // NOTE: make summands[-1] == 1 at top level of recursion
  partition(n, 0, summands+1, 0);  // NOTE: +1's are to make summands[-1] always safe inside recursion

  return 0;
}

如果您需要计算找到的总和，那么您可以添加一个额外的参数partition这是一个指向 (int) 迄今为止找到的总和计数的指针。您只需在打印基本情况下增加该计数。在 main 中，您将传递一个指向零初始化整数的指针，而在递归中，您只需传递该指针。当您返回主窗口时，您可以打印您找到的总和的数量。