Уникальные способы внесения изменений - не вывод ожидаемых значений

Question

Я пытаюсь создать программу, которая выводит все возможные уникальные способы внесения изменений для заданного ввода, используя ТОЛЬКО рекурсию и постоянную память (поэтому без циклов).

Для суммы в 25 центов это должны распечатать все возможные комбинации в следующем примере формата:

0*25+0*10+1*5+20*1
0*25+0*10+2*5+15*1
etc..

Где 0 * - это число четвертей (25), использованных в качестве примера

Проблема с моей программой заключается в том, что она распечатывается только:

0=0*25+0*10+0*5+25*1+

, а не остальные комбинации. Я подозреваю, что это из-за того, что я испортил методы printCombination и getLargerCombination (которые в основном являются рекурсивными методами, имитирующими для l oop), но я не могу понять, в чем проблема.

Вот весь код:

public class HW {

    static int[] coins = {25,10,5,1};
    static int[] counts = new int[coins.length];


    static void getCombinations(int[] counts, int startIndex, int totalAmount) {
        if(startIndex>= coins.length) {
            System.out.print(""+totalAmount+"=");
            printCombinations(0);
            return;
        }

        if(startIndex == coins.length - 1) {

            if(totalAmount%coins[startIndex]==0) //good combo 
            {
                //setting count of coins at start index
                counts[startIndex] = totalAmount/coins[startIndex];
                //move on to recursive calls
                getCombinations(counts, startIndex + 1, 0);
            }
        }

        else //still need to choose 0-N larger coins
        {
            getLargerCoins(0, totalAmount, startIndex);

        }


    }

    //Prints out all the possible combinations of change
    static void printCombinations(int i) {
        if(i >= coins.length) {
            System.out.print("\n");
            return;
        }
        System.out.print("" + counts[i] + "*" + coins[i] + "+");
        printCombinations(++i);
    }



    static void getLargerCoins(int j, int totalAmount, int startIndex) {
        if(j >= totalAmount/coins[startIndex]) {
            return;
        }
        //for every cycle in the loop, we choose an arbitray # of larger coins and proceed next
        counts[startIndex] = j;
        getCombinations(counts, startIndex+1, totalAmount-coins[startIndex]*j);
        j++;
    }

    public static void main(String[] args) {
        getCombinations(counts, 0, 25);
    }



}

**** РЕДАКТИРОВАНИЕ: *****

В методе getLargerCoins я просто повторил j ++, но забыл вызвать метод getLargerCoins для продолжения рекурсии. Исправил строку, написав:

getLargerCoins(++j, totalAmount, startIndex);

Вывод при запуске программы:

0=0*25+0*10+0*5+25*1+
0=0*25+0*10+1*5+20*1+
0=0*25+0*10+2*5+15*1+
0=0*25+0*10+3*5+10*1+
0=0*25+0*10+4*5+5*1+
0=0*25+1*10+0*5+15*1+
0=0*25+1*10+1*5+10*1+
0=0*25+1*10+2*5+5*1+

Однако он по-прежнему не выводит все возможные комбинации

Answer 1

Все, что вы можете решить с помощью oop, вы также можете решить с помощью рекурсии (не очень удобочитаемое, но рабочее решение):

public static void printCombinations(int[] coins, int amount) {
    printCombinations(coins, new int[coins.length], amount, 0);
}

private static void printCombinations(int[] coins, int[] counts, int amount, int index) {
    if (amount == 0) {
        print(coins, counts, 0, "");
    } else if (amount > 0) {
        printCombinationsLoop(coins, counts, amount, index);
    }
}

private static void printCombinationsLoop(int[] coins, int[] counts, int amount, int index) {
    counts[index]++;
    printCombinations(coins, counts, amount - coins[index], index);
    counts[index]--;
    if (index + 1 < coins.length)
        printCombinationsLoop(coins, counts, amount, index + 1);
}

private static void print(int[] coins, int[] counts, int index, String s) {
    if (counts[index] > 0) {
        if (!s.isEmpty())
            s += "+";
        s += counts[index] + "*" + coins[index];
    }
    if (index + 1 == coins.length)
        System.out.println(s);
    else
        print(coins, counts, index + 1, s);
}

Монеты должны быть уникальными, чтобы они могли работать должным образом.

Answer 2

Что заставляет вас думать, что рекурсия потребляет меньше памяти, чем циклы?

ТОЛЬКО рекурсия и постоянная память (так что никаких циклов).

Для вашей проблемы я думаю, что итеративный проще и быстрее.

public class MyClass {
  public static void main(String args[]) {

    int[] coins = {25,10,5,1};
    int[] counts = {0,0,0,0};

    long recStart = System.currentTimeMillis();
    recursive(25,0,coins,counts);
    long recEnd = System.currentTimeMillis();
    System.out.println("recursive millis: "+( recEnd- recStart));

    long iterativeStart = System.currentTimeMillis();
    iterative(25);
    long iterativeEnd = System.currentTimeMillis();
    System.out.println("iterative millis: "+( iterativeEnd- iterativeStart));

}

public static void recursive(int restValue, int level, int[] coins, int[] counts){
    if(restValue==0){
       System.out.println(counts[0]+"*25+"+counts[1]+"*10+"+counts[2]+"*5+"+counts[3]+"*1"); 
    }else if(restValue>0 && level<4){
        for(int i = 0; i<= restValue/coins[level]; i++ ){
             int rest= restValue - ( i*coins[level] );
             counts[level]=i;
             recursive(rest,level+1,coins,counts);
        }
    }
}

public static void iterative(int desiredValue){
    int q1=25;
    int q2=10;
    int q3=5;

    for(int i1 = 0; i1<= desiredValue/q1; i1++ ){
        int rest1= desiredValue - ( i1*q1 );

        for(int i2 = 0; i2<= rest1/q2; i2++ ){
            int rest2= rest1 - ( i2*q2 );
            for(int i3 = 0; i3<= rest2/q3; i3++ ){
                int rest3= rest2 - ( i3*q3 );
                System.out.println(i1+"*25+"+i2+"*10+"+i3+"*5+"+rest3+"*1");
            }
        }
    }
}

}