CODEWITHSUNDEEP
calgorithmrecursioncoin-change
newbie_old
newbie_old

Reputation: 510

algorithm-coin changing code mistake

Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter.

I have written below code but it is always returning one less than the actual answer. I want to know if this is the right way of coding up the solution?

#include <stdio.h>

int ways=0;
int remember[100] = {0};

void foo(int coin_denomination[], int size, int sum)
{
    int i;
    printf("%d\n", sum);
    if (sum==0) {
        ways++; 
        return; 
    }   
    if (remember[sum]==1)
        return; 
    remember[sum] = 1;
    if (sum < 0)
        return; 
    for(i=0;i<size;i++)
        foo(coin_denomination, size, sum-coin_denomination[i]);
}

int main()
{
    int coin_denomination[] = {1, 2, 3}; 
    int sum = 5;

    foo(coin_denomination, sizeof(coin_denomination)/sizeof(coin_denomination[0]), sum);
    printf("%d\n", ways);
    return 0;
}

Upvotes: 0

Views: 488

Answers (1)

NetVipeC
NetVipeC

Reputation: 4432

You need some change to foo method. Your problem is that with the variable remember you are not counting some solutions. The goal of variable remember is not correct, you are using for not processing the same coin collection multiple times but you are saving only the sum of the coin collection and the sum could be obtained with multiple coin collections (ex: 1 1 1 have same sum that 1 2 when you select the second, remember[3] would be 1 and not be passing this point, missing solution 1 2 2)

Other way of not repeating coin collection is needed, in this case, adding a parameter that represent the index of coin_denomination that is processing and only allow processing of coin after, the problem is solve.

Code (Tested with GCC 4.9.0):

#include <stdio.h>

int ways=0;

void foo(int coin_denomination[], int size, int sum, int coin_idx = 0)
{
    if (sum < 0)
        return;
    int i;
    printf("%d\n", sum);
    if (sum==0) {
        ways++; 
        return; 
    }   
    for(i=coin_idx;i<size;i++)
        foo(coin_denomination, size, sum-coin_denomination[i], i);
}

int main()
{
    int coin_denomination[] = {1, 2, 3}; 
    int sum = 5;

    foo(coin_denomination, sizeof(coin_denomination)/sizeof(coin_denomination[0]), sum);
    printf("%d\n", ways);
    return 0;
}

Upvotes: 2

Related Questions