C - Remove Duplicate Results in Recursive Function

Question

I have to create a recursive function that tells you the number of ways a number of cents can be made into change. (Using quarters, dimes nickels, and pennies).

So far, I have a recursive function that does that, however it counts the same combination more than once, so the number is too big. How do I remove the duplicate combinations?

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:

Input: 17 (cents)

Output: 80 ways **Output should be 6

What are duplicates? Seems to me that there is more than 6 ways of making 17 (cents) — PeCosta
– PeCosta, Commented Nov 11, 2015 at 1:43
@PeCosta A duplicate for example: 1 penny 1 nickel vs 1 nickel 1 penny. or in my case I believe the function is counting the same combination more than once. And there should only be 6 ways to make 17. — Felicia
– Felicia, Commented Nov 11, 2015 at 1:47

BLUEPIXY · Accepted Answer · 2015-11-11 02:46:30Z

4

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

edited Nov 11, 2015 at 2:46

answered Nov 11, 2015 at 2:02

BLUEPIXY

40.2k7 gold badges37 silver badges73 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Felicia Over a year ago

What exactly does the for loop do? I understand it I'm just having trouble putting it into words?

BLUEPIXY Over a year ago

Loop to calculate in each case the number of coins that can be used at that point.

Felicia Over a year ago

So, it starts at largest denomination, checks the number of coins that can be used at that point, and goes until kind[3] is reached. Correct?

Collectives™ on Stack Overflow

C - Remove Duplicate Results in Recursive Function

1 Answer 1

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related