發現硬幣的所有可能的組合，用遞歸

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; 
} 

什麼是我的遞歸算法的錯誤或者什麼是你的正確的代碼？ （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個組合。 （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找到它。

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