c - 找到选择 k 个数的方法数，这些数加起来为 n

Question

我需要找到选择k加起来的数字的方法数量n，其中1<= k <= n. 数字不得重复。我正在尝试一个递归解决方案，我认为它会陷入无限循环。

void noofways(int firstnumchosen,int sum,int numofnum)
{
   if(sum<0)
      return;

   if(sum==0 && numofnum!=0)
      return;

   if(sum==0 && numofnum==0){
      globalcount++;
      return;
   }

   if(numofnum<=0)
      return;

   // not choosing the first number
   noofways(firstnumchosen+1,sum,numofnum);

   //choosing the first number
   noofways(firstnumchosen+1,sum-firstnumchosen,numofnum-1);
}

globalcount这里是一个全局变量。要使用 3 个数字得到 7 的总和，我将调用该函数noofways(1,8,3);。为了让自己更清楚，解决方案集由（1,2,5），（1,3,4）等组成。

为什么我的函数会无限运行？

Answer 1

noofways(x, y, z)调用noofways(x+1, y, z)，所以 x 无限增长。

您需要测试 x 是否太大并在参数检查期间返回：

if (firstnumchosen > something)
    return;

这不是唯一的问题，但它是无限循环的原因。