java - 通过打印所有可能的方式递归硬币找零

Question

我已经尝试打印给出给定数量的所有路径。但是我的代码不能正常工作。我想我遗漏了一些点来打印所有可能的组合。例如；

• 如果 amount: 7 和 startCoin = 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