рекурсивный возврат makeChange

Напишите метод makeChange, который использует рекурсивный поиск с возвратом, чтобы найти все способы внести сдачу на заданную сумму денег, используя пенни (1 цент), пятак (5 центов), десять центов (10 центов) и четвертаки (25 центов).

Например, при внесении сдачи на 37 центов вы можете использовать:

• 1 квартал
• 1 копейка и 2 копейки
• 3 копейки и 7 копеек
• Или другие комбинации.

Ваш метод должен принимать один параметр: количество центов, на которое нужно внести сдачу.

Результатом вашего метода должна быть последовательность всех комбинаций каждого типа монет, которые в сумме составляют эту сумму, по одной на строку.

Например, если клиентский код содержит следующий вызов:

System.out.println(" P  N  D  Q");
System.out.println("------------");
makeChange(28);

Общий результат должен быть следующим:

 P  N  D  Q
------------ [3, 0, 0, 1] [3, 1, 2, 0] [3, 3, 1, 0] [3, 5, 0, 0] [8, 0, 2, 0] [8, 2, 1, 0] [8, 4, 0, 0] [13, 1, 1, 0] [13, 3, 0, 0] [18, 0, 1, 0] [18, 2, 0, 0] [23, 1, 0, 0] [28, 0, 0, 0]

Ключевым моментом в решении этой проблемы является представление о каждом достоинстве монеты (пенни, никель и т. д.) и переборе всех возможных номеров этой монеты (1 пенни, 2 пенни, ..., 28 пенни), чтобы увидеть, что комбинации могут быть сделаны, начиная с этого выбора. Например, в приведенном выше выводе сначала отображаются все комбинации, начинающиеся с 3 монет, затем все комбинации, начинающиеся с 8 центов, и так далее.

Поскольку поиск с возвратом включает в себя изучение набора вариантов, вы должны каким-то образом представлять номиналы монет в своем коде. Мы предлагаем вести список всех номиналов монет для обработки. По мере обработки различных значений монет вы можете изменять содержимое этого списка. Шаблон ниже является отправной точкой (вы можете скопировать/вставить его в текстовое поле кода, чтобы начать):

public static void makeChange(int amount) {
    List coinValues = new LinkedList();
    coinValues.add(1);    // penny
    coinValues.add(5);    // nickel
    coinValues.add(10);   // dime
    coinValues.add(25);   // quarter

// ... your code goes here ...

Вы можете предположить, что количество изменений, переданных вашему методу, неотрицательно, но оно может превышать 100.

Итак, вот мой код:

public static void makeChange(int amount){
    int[] acc = new int[4];
    makeChange(amount, acc);
}

private static void makeChange(int amount, int[] acc){
    if(amount == 0){
        System.out.print("[" + acc[0]);
        for(int i = 1; i < 4; i++){
            System.out.print(", " + acc[i]);
        }
        System.out.print("]");
        System.out.println();
    }
    if(amount > 0){
        acc[0]++;
        makeChange(amount - 1, acc);
        acc[0]--;
        acc[1]++;
        makeChange(amount - 5, acc);
        acc[1]--;
        acc[2]++;
        makeChange(amount - 10, acc);
        acc[2]--;
        acc[3]++;
        makeChange(amount - 25, acc);
        acc[3]--;
    }
}

и его вывод для вызова makeChange(28):

[28, 0, 0, 0]
[23, 1, 0, 0]
[23, 1, 0, 0]
[23, 1, 0, 0]
[23, 1, 0, 0]
[23, 1, 0, 0]
[23, 1, 0, 0]
[18, 2, 0, 0]
[18, 0, 1, 0]
[23, 1, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 0, 1, 0]
[23, 1, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 0, 1, 0]
[23, 1, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 0, 1, 0]
[23, 1, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 0, 1, 0]
[23, 1, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 0, 1, 0]
[13, 1, 1, 0]
[23, 1, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 0, 1, 0]
[13, 1, 1, 0]
[13, 1, 1, 0]
[23, 1, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 0, 1, 0]
[13, 1, 1, 0]
[13, 1, 1, 0]
[13, 1, 1, 0]
[23, 1, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 0, 1, 0]
[13, 1, 1, 0]
[13, 1, 1, 0]
[13, 1, 1, 0]
[13, 1, 1, 0]
[23, 1, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]

... (есть сотни строк вывода)

Может кто-нибудь сказать мне, почему создается дублированный вывод? Большое спасибо!