Java - SubSet和遞歸遞歸遞歸圖

Question

我有一個理解遞歸代碼的問題，我試圖畫出樹跟隨，但有些東西對我來說還不清楚。 有人可以幫助我理解代碼片段，並在頁面上繪製，或繪製或任何其他軟件，遞歸樹，以便我可以完全理解代碼。

爲什麼會有兩個遞歸？ 我不明白第二次遞歸如何工作（在||之後）。

public static boolean hasSum(int[] array, int start, int sum) { 
    if (sum == 0) 
     return true; 

    if (start > array.length - 1) 
     return false; 

    return hasSum(array, start + 1, sum - array[start]) 
      || hasSum(array, start + 1, sum); 

} 

非常感謝您的幫助

Answer 1

搜索到的子集和（即sum）可以包括當前元素（array[start]）或（因此||）不包括當前元素。

如果它包括array[start]，我們應該找到索引start+1開始的子數組的子集，其總和爲sum - array[start]。

這是由hasSum(array, start + 1, sum - array[start])處理。

如果它不包括array[start]，我們應該找到子陣列的一個子集開始在指數start+1其總和sum（即，因爲目前的元素不參與的總和，我們必須找到在一個更小的陣列中相同的總和）。

這是由hasSum(array, start + 1, sum)處理。

因此這兩個遞歸調用。