What's wrong with this solution of coin change problem?

Question

Here is the coin change problem from hackerrank(https://www.hackerrank.com/challenges/coin-change). It asks to compute a total number of ways to make a change for N using coins of given denominations.

For example, there are four ways to make a change for 4 using coins of denominations 1, 2, and 3. They are - {1,1,1,1}, {1,1,2}, {2,2}, {1,3}.

I've tried to implement a recursive solution using dynamic programming in java. My solution is based on the idea that, for each coin of given denominations, we recur to see if total can be reached by choosing the coin or not. If choosing the current coin results in the solution, we update a total number of ways. But the solution doesn't work.

Here's the implementation

public static long getWays(long n, long[] c) {
        Map<String, Long> map = new HashMap<String, Long>();
        return fun(n, c, 0, map);
    }
public static long fun(long n, long[] c, int i, Map<String, Long> memo){
    if(n == 0) return 1;
    if(i >= c.length) return 0;
    if(n < c[i]) return 0;
    String key = n + "_" + i;
    if(memo.containsKey(key)) return memo.get(key);
    long ways = fun(n, c, i+1, memo) + fun(n-c[i], c, i, memo);
    memo.put(key, ways);
    return ways;
}

This gives me the wrong answer. For example, there are 5 ways to make a change for 10 using coins of {2, 5, 3, 6} but it returns 4 as the output.

where am I wrong?

fun(n, c, i+1, memo) + fun(n-c[i], c, i +1 , memo); — Joop Eggen
@GurwinderSingh no, it's not. Different approach and well clarified specific question on his individual code. — harmonica141

Adam Lerman Adam Lerman · Accepted Answer · 2019-07-30T10:21:19

At first glance, it looks like your solution will skip solutions if a coin higher than the remaining value is in a position before the i'th position in the array. Think about the case where n=5 and c=[10,5]. The answer there should be 1.

In your code, it would get to the if statement checking if n

if(n < c[i]) return 0;

And would return 0.

What's wrong with this solution of coin change problem?

1 Answers