Ошибка рекурсивной попытки монеты Java

Question

Я пытаюсь изменить проблему с изменением монеты java, чтобы перечислить все возможные наборы изменений для n.

Моя логика следует так:

while n >= denom m { 
array[]+= denom m 
n-= denom m 
} 
list.add[array[]] 

return coinChanger(++denom) 

Мой код:

public List<Integer> makeChange(int change) { 

    int[] denominations; 
    denominations = new int[]{1, 5, 10, 25}; 

    return changeMaker(change, denominations, 0); 
} 

public List<Integer> changeMaker(int change, int[] denominations, int index) { 
    List<Integer> resultsList = new ArrayList<Integer>(); 
    int[] resultDenom; 
    resultDenom = new int[4]; 

    if (change <= 1) { 
     return resultsList; 
    } 

    while (change >= denominations[index]) { 
     resultDenom[index] += denominations[index]; 
     System.out.println("ResultsDenom: " + resultDenom[index]); 
     change -= denominations[index]; 
    } 
    resultsList.add(resultDenom[index]); 

    for (int val : resultDenom) { 
     System.out.println(val); 
    } 


    if (change > denominations[index]) {  
     return changeMaker(change-=denominations[index], denominations, ++index);  

    } 
    return resultsList; 
} 

Это выводит только один набор всех перечислений:

ВЫВОД:

27 
0 
0 
0 
RESULT CHANGE PERMUTATIONS LIST: [27] 

Вопросы:

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

Спасибо!

* EDIT **

public List<Integer> makeChange(int change) { 

    int[] denominations; 
    denominations = new int[]{25, 10, 5, 1}; 

    return changeMaker(change, denominations, 0); 
} 

public List<Integer> changeMaker(int change, int[] denominations, int index) { 
    List<Integer> resultsList = new ArrayList<Integer>(); 
    int[] resultDenom; 
    resultDenom = new int[4]; 

    if (change <= 1) { 
     return resultsList; 
    } 

    if (index > 3) { 
     return resultsList; 
    } 
    //if 27 >= 25 
    if (change >= denominations[index]) { 

     //[+25, 0, 0, 0] 
     resultDenom[index] += denominations[index]; 

     //{ LIST } <--- [25, 0, 0, 0] 
       //List now contains { [25, 0, 0, 0], }, still need all other permutations 
     resultsList.add(resultDenom[index]); 

     //27 - 25, 
     return changeMaker(change-=denominations[index], denominations, ++index);  

    } 
    return resultsList; 
} 

ХОЧЕТ ВЫХОДА: Список списков ... 27 центов:

LIST{ [1, 0, 0, 2], [0, 2, 1, 2], [0, 1, 3, 2]... etc}

Answer 1

Ваш код кажется немного запутанным для проблема, которую вы пытаетесь решить

Попробуйте реализации этого псевдо-код

getChange(int totalCents) 
    { 
     if (totalCents > 25) 
     { 
     print "25"; 
     getChange(totalCents - 25); 
     } 
     else (totalCents > 10) 
     { 
     // same for 10 
     } 
     else (totalCents > 5) 
     { 
     // same for 5 
     } 
     else 
     { 
     // print out number left as pennies 
     } 
    } 

Вы можете легко заменить, если заявления с закодированными значениями с индексами массива и для цикла, и печатью с тем не менее вы хотите записать значение. Надеюсь, это поможет.

Answer 2

решение Простейшие является рекурсию в двух вариантах на каждом шаге (если вы не законченный):

1. Продолжить с текущей монеты: Добавить его в список и Recurse.
2. Переключить на следующую монету: Прирастить монету и повторить.

Должно выглядеть так:

public class Coins { 
    static final int[] DENOMINATIONS = {25, 10, 5, 1}; 

    public static void change(int amount) { 
    change(amount, new ArrayList<Integer>(), 0); 
    } 

    private static void change(int remaining, List<Integer> coins, int pos) { 
    if (remaining == 0) { 
     System.out.println(coins); 
    } else { 
     if (remaining >= DENOMINATIONS[pos]) { 
     coins.add(DENOMINATIONS[pos]); 
     change(remaining - DENOMINATIONS[pos], coins, pos); 
     coins.remove(coins.size() - 1); 
     } 
     if (pos + 1 < DENOMINATIONS.length) { 
     change(remaining, coins, pos + 1); 
     } 
    } 
    } 
} 

Если вы хотите, чтобы собрать списки, вам нужно сделать копию списка, где добавляется монета (вместо того, чтобы удалить его после возвращения из вызова).