Number of ways to give coin change

Question

I am trying to solve a problem of coin change using memoization and recursion. But there is something glitch in my code it is givng me wrong output.

    public static int coinChangeMemo(int coins[], int n) {
        int [][] memo = new int[n+1][coins.length+1];
        for (int row = 0; row < memo.length; row++) {
            for (int col = 0; col < memo[row].length; col++) {
                memo[row][col] =-1; 
            } 
        }
        return coinChangeMemoHelper(coins, n, 0, memo);
    }


    private static int coinChangeMemoHelper(int coins[], int n, int index, int memo[][]) {
        if(n == 0) {
            return 1;
        }
        if(index >= coins.length) {
            return 0;
        }
        if(n <= 0) {
            return 0;
        }

        if(memo[n][index] != -1) {
            return memo[n][index];
        }
        int withUsingCurrent = coinChangeMemoHelper(coins, n-coins[0], index, memo);
        int withoutUsingCurrent  = coinChangeMemoHelper(coins, n, index+1, memo);

        memo[n][index] = withUsingCurrent + withoutUsingCurrent;
        return withUsingCurrent + withoutUsingCurrent;

    }

    public static void main(String[] args) {
        //coins denominations are 1, 2

        int coins[] = {1,2};
        //i want a change of 4 
        int sum = 4;

        System.out.println(coinChangeMemo(coins, sum));

Coins denominations available 1,2

I want a sum of 4.

possible ways are

(1,1,1,1)
(1,2,1)
(2,2)

I am expecting an output 3, but it is returning me 5

[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — Kartik, Jul 05 '19 at 07:05
I have no idea what your code is supposed to do, or why it would return 3. if you have coins of 1 and 2 value, and your amount is 4, I would expect it to return 2 coins of 2 — Stultuske, Jul 05 '19 at 07:07
@Stultuske I want to return number of ways amount 4 is given. I have updated the description. — Rohit Sharma, Jul 05 '19 at 07:16
my guess, your code considers 2,1,1 - 1,1,2 - 1,2,1 as different solutions. — Stultuske, Jul 05 '19 at 07:18

score 1 · Answer 1 · answered Jul 05 '19 at 08:24

You need to make 2 changes in your code:-> 1.you can combine last 2 base case as : if(index==coins.length || n<0){ return 0; } 2.you have done mistake in recursive call to withUsingCurrent: UPDATE IT LIKE THIS BELOW int withUsingCurrent = coinChangeMemoHelper(coins, n-coins[index], index, memo);

Number of ways to give coin change

1 Answers1