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;

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