Time complexity of algorithm for different ways of using coins to give the return


  • 0
    S

    Here is the question
    Given coins of denomination {25, 10, 5, 1}, what are the different ways to return 50. For instance

    a) 2 coins of denomination 25
    b) 1 coin of denomination 25, 2 coins of denomination 10, 1 coin of denomination 5

    Here is my solution for that

        
        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) {
            CoinChange.coinChangeWays(50);
        }
    
    }
    

    I am having some problems getting the time complexity of this algorithm. I have definitely used memoization. But still we have to iterate through all the results of the subproblem. Given that the number of coins =n and the sum S, the time complexity is definitely more than O(nS). It looks exponential to me O(S^n). But I am not sure. Any help in the analysis will be appreciated. Thanks


Log in to reply
 

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