minimum coin top-down solution is not giving expected results

Question

we had an intern solve minimum coin problem using top-down approach. The problem statement is given set of coins, return the minimum coins required to form the sum. Additionally return the coins that form the sum.

Eg: coins = {7, 3, 2, 6}, total = 13,
result should be minCoins = {2}, coinsUsed = {7,6}

Here is the code

package dp;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class MinimumCoin {

    public static void main(String[] args) {

        int total = 13;
        int coins[] = {7, 3, 2, 6};

        Result rs  = minCoin(coins, total, new HashMap<>());
        System.out.println(rs.min);
        System.out.println(rs.coins);

    }

    public static Result minCoin(int[] coins, int total, Map<Integer, Result> memo) {

        if (total == 0) {
            return new Result();
        }

        if (memo.containsKey(total)) {
            return memo.get(total);
        }

        int min = Integer.MAX_VALUE;
        List<Integer> coinsSoFar = new ArrayList<>();

        for (int i = 0; i<coins.length; i++) {

            if (coins[i] > total) {
                continue;
            }

            Result rs = minCoin(coins, total-coins[i], memo);
            coinsSoFar.add(coins[i]);
            if (rs.min > min) {
                min = rs.min;
                coinsSoFar.addAll(rs.coins);
            }
            else {
                coinsSoFar.remove(coinsSoFar.size()-1);
            }
        }

        min =  (min == Integer.MAX_VALUE ? min : min + 1);

        Result rs = new Result(min, coinsSoFar);

        memo.put(total, rs);
        return rs;
    }

    public static class Result {

        private int min;
        private List<Integer> coins = new ArrayList<>();

        private Result() {}
        private Result(int min, List<Integer> coins) {
            this.min = min;
            this.coins = coins;
        }


    }
}

The code looks good for the most part. but doesn't return expected results. when executed with above input, the program returns INT.MAX as minCoins and the list is empty.

Any hints on where the code went wrong? Thanks

Answer 1

Well, you initialize min to Integer.MAX_VALUE, and then have the following code:

if (rs.min > min) {
    min = rs.min;
    coinsSoFar.addAll(rs.coins);
}

As you can see, rs.min is an int and will never be greater than min (which is Integer.MAX_VALUE).

The only other place you change min at is the following:

min =  (min == Integer.MAX_VALUE ? min : min + 1);

However, because min is still Integer.MAX_VALUE, it will never change. I'll let you take it from here.