C - 删除递归函数中的重复结果

我必须创建一个递归函数，告诉您可以将多少美分变成零钱的方法。 （使用 25 美分、10 分、5 分、5 分、5 分硬币）。

到目前为止，我有一个递归函数可以做到这一点，但是它多次计算相同的组合，所以数字太大了。如何删除重复的组合？

Code:

 #include <stdio.h>
//Prototypes
int coins(int);

int main(void){
    //Declarations
    int num;

    //Get user input
    printf("Enter an amount of change in cents: ");
    scanf("%d", &num); //Change to fgets

    //Call function
    printf("There are %d ways to make change for %d cents.\n", (coins(num)), num);
}

int coins(int amt){
    //Declarations
    int ways=0;

    //Base Case
    if(amt == 0){
        return 1;
    }

    //int ways=0; More efficient after base case.

    if(amt >= 1){
        ways+=coins(amt-1);
    }
    if(amt >= 5){
        ways+=coins(amt-5);
    }
    if(amt >= 10){
        ways+=coins(amt-10);
    }
    if(amt >= 25){
        ways+=coins(amt-25);
    }

    return ways;
}

Example:

输入：17（美分）

输出：80路 **输出应该是6

#include <stdio.h>

int coins(int, int);

int main(void){
    int num;

    printf("Enter an amount of change in cents: ");
    scanf("%d", &num);

    printf("There are %d ways to make change for %d cents.\n", coins(num, 0), num);
    return 0;
}

int coins(int amt, int kind){
    static int kinds[4] = {25, 10, 5, 1};
    int ways=0, i, n;

    if(kinds[kind] == 1)//always divisible
        return 1;

    n = amt / kinds[kind];
    for(i = 0; i <= n; ++i)
        ways+=coins(amt-kinds[kind]*i, kind + 1);

    return ways;
}