find all the possible combination of coins, implementing by recursion

Question

Solve the problem by recursion:

using three type coins include 1 yuan, 2 yuan and 5 yuan, plus to 10 yuan, how many combinations?

The following is my code :

int coinNum(int num){
   if(num>=0){
       if(num==0)
           return 1;
       else 
           return coinNum(num-5)+coinNum(num-2)+coinNum(num-1);
   }else
       return 0;
 }

int main(){
   int num=coinNum(10);
   printf("%d\n",num);//the result is 128
   system("pause");
   return 0;
}

What's the error of my recursion algorithm or what's your right code ?
question supplement :
1. (5,2,2,1) and (2,5,2,1) should be counted as 1 combination .
2. the following is my code of the enumeration algorithm .

void coin(){
  int i,j,k,count=0;
  for(i=0;i<=10;i++)
    for(j=0;j<=5;j++)
        for(k=0;k<=2;k++)
            if((i+2*j+5*k)==10){
                count++;
                printf("one yuan :%d，2 yuan :%d，5 yuan :%d\n",i,j,k);
            }

   printf("总方法数%d\n",count);//the result is 10
 }

Answer 1

Your code is counting the number of permutations that add up to 10. You want combinations. That means (5,2,2,1) and (2,5,2,1) should be counted as 1 combination.

In this case, the answer should be 10: (5,5), (5,2,2,1), (5,2,1,1,1), (5,1,..1), (2,2,2,2,2), (2,2,2,2,1,1), (2,2,2,1,1,1,1), (2,2,1,..1), (2,1,..1), and (1,..1).

Try this code:

int coinNum(int num, int *coins){
  if (num == 0) return 1;
  if (num < 0 || !*coins) return 0;
  return coinNum(num - *coins, coins) + coinNum(num, coins+1);
}

int main(){
  int coins[] = {5,2,1,0}; // don't forget the 0 or the program won't end

  int num=coinNum(10,coins);
  printf("%d\n",num); // the result is 10
  system("pause");
  return 0;
}

The code above tries all combinations until the sum equals or exceeds the desired sum. Note that this is not the most efficient algorithm to solve this problem, but the most simple one. For better algorithms, you should probably look for it at Computer Science Stack Exchange.

Answer 2

Another simple algorithm, using idea to generate not decreasing sequence of coins.

int coinNum(int num, int min_coin) {
  if (num == 0) {
    return 1;
  } else if (num < 0) {
    return 0;
  } else {
    int res = coinNum(num - 5, 5);
    if (min_coin <= 1) {
      res += coinNum(num - 1, 1);
    }
    if (min_coin <= 2) {
      res += coinNum(num - 2, 2);
    }
    return res;
  }
}

int main(){
  int num = coinNum(10, 1);
  printf("%d\n", num);
  return 0;
}