递归硬币更改通过打印所有可能的方式进行

Question

我尝试打印所有给出给定数量的路径。但是我的代码无法正常工作。我想我缺少一些点来打印所有可能的组合。例如;

• 如果金额：7 且起始币 = 25，程序需要给我：{5,1,1} 和 {
1,1,1,1,1,1,1}。

你能帮我解决这些问题吗？

注意：最好是 Java 解决方案

class Solution {
      static int[] coinSet = {1,5,10,25};
      static List<List<Integer>> possibleWays = new ArrayList<>();
      static List<Integer> currentWay = new ArrayList<>();
      private static int makeChange(int amount, int startCoin){
        boolean flag = false;
        for(int i =0 ; i < coinSet.length ; i++){
          if(coinSet[i] == startCoin) {
            flag =true;
          }
        }
        if(!flag){
          throw new IllegalArgumentException("startCoin has to be in the specified range");
        }
        int nextCoin = 0;
        switch(startCoin) {
          case 25:
            nextCoin = 10;
            break;
          case 10:
            nextCoin = 5;
            break;
          case 5:
            nextCoin = 1;
            break;
          case 1:
            possibleWays.add(currentWay);
            currentWay = new ArrayList<>();
            return 1;
        }
        int ways = 0;
        for(int count = 0; count * startCoin <= amount; count++){
          ways += makeChange(amount - (count * startCoin),nextCoin);
        }
        return ways;
      }    
      public int calculateNumberOfWays(int amount, int startCoin) throws Exception {
        if (amount == 0) {
          throw new Exception();    }
        return makeChange(amount, startCoin);
      }
      public static void main(String[] args) {
        System.out.println(makeChange(5,25));
        System.out.println(possibleWays);
      }
    }

Answer 1

这可以使用回溯来解决，但效率不高，下面是工作 java 代码

/**
 * Created by sumit sharma on 3/1/2016.
 */
import java.util.ArrayList;
import java.util.Date;
import java.util.List;
import java.util.Random;
public class Main {
    static int[] coinSet = {1,5,10,25};
    static List<List<Integer>> possibleWays = new ArrayList<>();
    static List<Integer> currentWay = new ArrayList<>();
    public static void main(String[] args) {
        List<Integer> countOfCoins = new ArrayList<>();
        makeChange(7, 0, countOfCoins);
        //System.out.print(possibleWays);
    }
    private static int makeChange(int amount, int startCoinIdx, List<Integer> coinsSoFar) {
        if(startCoinIdx == coinSet.length){
            if(amount == 0){
                possibleWays.add(coinsSoFar);
                System.out.println(coinsSoFar);
            }
            //System.out.println(coinsSoFar);
            return 0;
        }
        for(int count = 0;(count*coinSet[startCoinIdx]) <= amount;count++){
            List<Integer> temp = new ArrayList<>();
            for(int i = 0;i < coinsSoFar.size();i++) temp.add(coinsSoFar.get(i));
            for(int i = 0;i < count;i++) temp.add(coinSet[startCoinIdx]);
            makeChange(amount - (count * coinSet[startCoinIdx]),startCoinIdx+1, temp);
            temp.clear();
        }
        return 0;
    }
}

链接到 Ideone 上的解决方案：http://ideone.com/kIckmG