Coin change problem with the actual ways to make the change


  • 0
    S

    The problem is different from the usual coin change problem. Now we not only have to find the number of ways to make the change but the actual ways to give the change. For example

    If we have coins of denominations D = {50,25,5,1} and target T = 100, the solution will be list of ways to make the change like

    {{2 - 50 denom coins },{1 - 5 denom coins, 2 - 25 denom coins }.......}

    Here is my solution for that

    public class CoinChange3 {
    
        private static class Element {
            int value;
            int count;
    
            public Element(int value, int count) {
                this.value = value;
                this.count = count;
            }
        }
    
        public static List<String> coinChangeWays(int sum) {
            List<String> result = new ArrayList<>();
            Map<Integer, Map<Integer, List<List<Element>>>> map = new HashMap<>();
            List<List<Element>> sol = helper(sum, 25, map);
            for(List<Element> candidate: sol) {
                result.add(serialize(candidate));
            }
            for(String value: result) {
                System.out.println(value);
            }
            return result;
        }
    
        private static List<List<Element>> helper(int sum, int index, Map<Integer, Map<Integer, List<List<Element>>>> map) {
            if(map.containsKey(index) && map.get(index).get(sum) != null) {
                return map.get(index).get(sum);
            }
            int nextIndex = 0;
            List<List<Element>> list = new ArrayList<>();
            switch(index) {
                case 25:
                    nextIndex = 10;
                    break;
                case 10:
                    nextIndex = 5;
                    break;
                case 5:
                    nextIndex = 1;
                    break;
                case 1:
                    List<Element> solList = Arrays.asList(new Element(1, sum));
                    list.add(solList);
                    return list;
            }
            for(int i=0; i*index<= sum; i++) {
    
                List<List<Element>> subSolution = helper(sum-i*index, nextIndex, map);
    
                for(List<Element>sol: subSolution) {
                    List<Element> candidate = new ArrayList<>();
                    candidate.add(new Element(index, i));
                    candidate.addAll(sol);
                    list.add(candidate);
                }
            }
            Map<Integer, List<List<Element>>> innerMap = new HashMap<>();
            if(map.get(index) != null) {
                innerMap = map.get(index);
            }
            innerMap.put(sum, list);
            map.put(index, innerMap);
            return list;
        }
    
        private static String serialize(List<Element> elements) {
            StringBuilder sb = new StringBuilder();
            for (Element elem: elements) {
                sb.append(elem.value + " " + elem.count + " ");
            }
            return sb.toString();
        }
    
        public static void main(String[] args) {
            CoinChange3.coinChangeWays(50);
        }
    
    }
    

    I have used memoization to prevent solving the same subproblem again. However, since we have to iterate through the whole solution set from the next subproblem, the time complexity is higher than O(nS) where n is the number of coins and S is the target sum. Is the time complexity exponential for this?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.