CODEWITHSUNDEEP
calgorithmrecursion
OneMoreError
OneMoreError

Reputation: 7728

Finding number of ways to select k numbers that add upto n

I need to find the number of ways to select k numbers that add upto n, where 1<= k <= n. The numbers are not to be repeated. I am trying a recursive solution, which I think runs into an infinite loop.

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 is a global variable here. To get the sum of 7 by using 3 numbers, I will be calling the function noofways(1,8,3);. To make myself more clear, the solution set consists of (1,2,5), (1,3,4) and so on.

Why fdoes my function run infinitely?

Upvotes: 1

Views: 350

Answers (1)

Andrew Tomazos
Andrew Tomazos

Reputation: 68658

noofways(x, y, z) calls noofways(x+1, y, z), so x grows unbounded.

You need to test if x is too large and return during parameter check:

if (firstnumchosen > something)
    return;

This isn't the only problem, but it is the cause of the infinite loop.

Upvotes: 3

Related Questions