Why doesn't my Counting Change answer work?
vcoder
68

This is the problem:
Given an integer array containing the available denominations of coins in descending order, write a method to compute the number of possible ways of representing a monetary amount in cents.
For simplicity, assume that there are an infinite number of coins available for each coin denomination in the array.
This is the problem header
public static int makeChange(int[] coins, int amount) {

My solution:

private static int numWays = 0;

public static int makeChange(int[] coins, int amount) {
    helper(coins, amount, 0);
    return numWays;
}
public static void helper(int[]coins, int amount, int i){
    if (i >= coins.length){
        return;
    }
    int val = amount - coins[i];
    if (val < 0){
        return;
    }
    if (val == 0){
        numWays++;
        return;
    }
    helper(coins, val, i + 1);
    helper(coins, amount, i + 1);
    helper(coins, val, i);
}

I think I understand why the official solution works... but I still don't get how mine doesn't arrive at the same result. This is what the offical solution is:

public static int makeChange(int[] coins, int amount) {
    return helper(coins, amount, 0);
}
public static int helper(int[]coins, int amount, int cur){
    if (amount < 0){
        return 0;
    }
    if (amount == 0){
        return 1;
    }
    int ans = 0;
    for (int i = cur; i < coins.length; i++){
        ans += helper(coins, amount - coins[i], i);
    }
    return ans;
}
Comments (1)