0
我試圖打印給定數量的所有路徑。但我的代碼無法正常工作。我想我錯過了一些要打印所有可能的組合。例如;遞歸硬幣更改通過打印所有可能的方式進行製作
- 如果量: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);
}
}
嗨,你可以看看這裏尋求幫助:http://info.mcip.ro/?cap=Backtracking&prob=368。這不是Java,但它解決了你的問題:)。 如果你仍然困惑,研究一下回溯問題。 –
您是否清楚該解決方案的時間複雜度和空間複雜度?我想這是O(n!),但我不確定。 –
關於複雜性:您可以通過* dynamic programming *避免指數運行時間。當你擁有像5這樣的值的所有解決方案時,像6這樣的值的解決方案就是(所有解1)x(所有解的5)。 – Marco13