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

• 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) {
}
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));
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<>();
}
}
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

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