以遞歸方式找到子集總和的錯誤java

n是一個子集，它包含所需的總和（目標）大小：所以

set[] = {5,6,9,-1,4,2} 
n = 3 
sum = 10

將等同於真實的，因爲大小爲3，總結的子集10是{9} -1,2-

public static boolean isSubsetSum(int[] set, int n, int sum) { 
int[] copy = new int[set.length - 1]; 
System.arraycopy(set, 0, copy, 0, set.length - 1); 

// Base Cases 
    if (sum == 0 && n == 0) 
    return true; 
    if (set.length == 0)  // fixed base case. 
    return false; 

    if (set[set.length - 1] > sum) { 
    return isSubsetSum(copy, n, sum); 
    } 

    return isSubsetSum(copy, n, sum) || isSubsetSum(copy, n-1, sum - set[set.length-1]); 
}

來源

2014-03-06 user3362954

我覺得你的主要問題是，當你調用

return isSubsetSum(copy, n, sum)

n和sum不會減少，所以它們永遠不會達到零。在n和sum被更改的末尾確實有呼叫，但通過閱讀代碼可以清楚地看出，對於某些功能輸入，您永遠不會到達那裏。

來源

2014-03-06 23:33:24 hlovdal

我已經經歷了與子集{-4,0,4}，n = 2（或3），總和需要爲0 ...任何建議？ – user3362954

您看到的遞歸錯誤（至少部分）是因爲您的return語句的左側。

copy是一組確切的副本，所以調用isSubsetSum(copy, n, sum)與調用isSubsetSum(set, n, sum)相同。如果其中一個基本案例不適用於設置，則它也不適用於複製，導致||評估的左半部分（其首先評估）的無限遞歸。因此，程序永遠不會找到問題的解決方案，並且最終你會希望看到遞歸錯誤（或者它將永遠保持持續不斷！）

爲了避免這種情況，您需要修改遞歸調用在return語句中只處理問題的一個子集。

來源

2014-03-06 23:33:44 emerssso

哪個返回語句？你會如何推薦遞減？ – user3362954

我指的是最後的return語句：'return isSubsetSum（copy，n，sum）|| isSubsetSum（copy，n-1，sum-set [set.length-1]）;'。 – emerssso

調試你的代碼後，我看到你得到這個錯誤：java.lang.NegativeArraySizeException，你得到的是因爲當你的數組大小爲0時，你嘗試在你的方法的第二行復制它的長度爲-1。
更改線條的順序（在開始處檢查此基本情況），並且您的方法將正常工作。

來源

2014-03-06 23:42:09

以遞歸方式找到子集總和的錯誤java

回答

相關問題