給定來自多個面額的 1 個硬幣（例如 1 個硬幣、5 個硬幣、16 個硬幣）和一個總和，回傳 true 或 false 以確定是否可以進行總和。
boolean go(int[] coins, int goal)
{
//Will set each time, but shouldn't matter as toggle is at bottom
boolean ans = false;
//loop running in recursion till founds ans
//Really bad time complexity lol
for (int i = 0; i < coins.length && (!ans); i ) {
if ((goal - coins[i] == 0) || goal == 0) {
return true;
}
if (goal > coins[i]) {
int[] red = new int[coins.length - 1];
//it necessary because making list with one less
int it = 0;
//Setting new list to avoid runtime
for(int x = 0; x < coins.length; x ){
if(!(i == x)){
red[it] = coins[i];
it = 1;
}
}
//Run with new list
ans = go(red, goal - coins[i]);
}
}
return ans;
}
到目前為止，這是我的代碼。我已經使它遞回，但其中一個測驗用例在不應該回傳 true 時回傳 true。測驗用例特別是 [111, 1, 2, 3, 9, 11, 20, 30]，目標是 8；這應該回傳 false（因為它加起來不能達到 8），但在本例中回傳 true。
其他測驗用例作業正常，所以我相信我的代碼有某種例外。
我試圖將基本案例向上移動，并進行反向變化......
boolean go(int[] coins, int goal)
{
boolean ans = false;
if(goal == 0){
return true;
}else if(goal < 0){
return false;
}
for (int i = 0; i < coins.length && (!ans); i ) {
if (goal >= coins[i]) {
int[] red = new int[coins.length - 1];
int it = 0;
for(int x = 0; x < coins.length; x ){
if(!(i == x)){
red[it] = coins[i];
it = 1;
}
}
ans = go(red, goal - coins[i]);
}
}
return ans;
}
是我試過的，但基本情況似乎沒有任何影響
uj5u.com熱心網友回復：
錯誤出在您復制 coins 陣列中：red[it] = coins[i]真的應該是red[it] = coins[x]...
對于時間復雜度，您實際上不必在方法內進行回圈。每個面額要么是總和的一部分，要么不是總和的一部分，因此您始終可以洗掉第一個面額并在有或沒有它的情況下進行測驗：
boolean go(int[] coins, int goal) {
if(goal == 0)
return true;
else if(coins.length == 0 || goal < 0)
return false;
else {
int[] tailOfCoins = Arrays.copyOfRange(coins, 1, coins.length);
return go(tailOfCoins, goal) || go(tailOfCoins, goal - coins[0]);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/533955.html
標籤：爪哇递归