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("%d\n",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 :%d\n",i,j,k);
            }

   printf("总方法数%d\n",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("%d\n",num); // the result is 10
  system("pause");
  return 0;
}

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