Это другая задача. Учитывая бесконечное количество монет достоинством 25, 10, 5 и 1, найдите различное количество способов использовать монеты, чтобы в сумме получить заданное значение.
public void getCombination(int[] coins, int sum, int start, ArrayList<Node> currentValues) {
if(sum == 0) {
for(Node n: currentValues) {
System.out.print(n + " ");
}
System.out.println();
return;
}
int next_denom = 1;
switch(start) {
case 25:
next_denom = 10;
break;
case 10:
next_denom = 5;
break;
case 5:
next_denom = 1;
break;
case 1:
currentValues.add(new Node(1, sum));
for(Node n: currentValues) {
System.out.print(n);
System.out.print(" ");
}
System.out.println();
currentValues.remove(currentValues.size()-1);
return;
}
for(int i=0; i*start<=sum; i++) {
currentValues.add(new Node(start,i));
getCombination(coins, sum-(i*start), next_denom, currentValues);
currentValues.remove(currentValues.size()-1);
}
}
Я думаю, что временная сложность равна O (N ^ d), где N - заданная сумма, а d - количество монет. Глубина рекурсии равна d, поэтому глубина дерева рекурсии не превышает d. В худшем случае на каждом уровне количество ответвлений от данного узла будет равно N.
