C - 找到所有可能的硬币组合，通过递归实现

Question

通过递归解决问题：

使用三种类型的硬币包括1元，2元和5元，加上到10元，有多少种组合？

以下是我的代码：

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("%dn",num);//the result is 128
   system("pause");
   return 0;
}

我的递归算法有什么错误，或者你的正确代码是什么？问题补充：1.（5，2，2，1）
和（2，
5，2，1）应算作1组合。
2.以下是我的枚举算法代码。

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 :%dn",i,j,k);
            }
   printf("总方法数%dn",count);//the result is 10
 }

Answer 1

您的代码正在计算总计为 10 的排列数。你想要组合。这意味着 （5，2，2，1） 和 （2，5，2，1） 应算作 1 个组合。

在这种情况下，答案应该是 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）、和 （1,..1）.

试试这个代码：

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("%dn",num); // the result is 10
  system("pause");
  return 0;
}

上面的代码尝试所有组合，直到总和等于或超过所需的总和。请注意，这不是解决此问题的最有效算法，而是最简单的算法。对于更好的算法，您可能应该在Computer Science Stack Exchange上查找它。

Answer 2

另一种简单的算法，使用想法来生成不递减的硬币序列。

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("%dn", num);
  return 0;
}