跟蹤遞歸

Question

我正在學習遞歸，並且在追蹤遞歸方面有困難。 這是我的問題，我有解決方案，它工作得很好。 我被卡住了一些點，無法繼續跟蹤。

問題： 給定一個int數組，是否有可能選擇一組int，使得該組相加到給定的目標。

解決方案：

public static boolean groupSum1(int start, int[] nums, int target) 
     { 
      if (start >= nums.length) return (target == 0);    
      if (groupSum1(start + 1, nums, target - nums[start])) return true;    
      if (groupSum1(start + 1, nums, target)) return true;    
      return false; 
     } 

開始= 0（其中我們必須開始陣列）

NUMS [] = {10,8,6}目標= 16

請幫幫我跟蹤問題？

Answer 1

開始通過編號線

public static boolean groupSum1(int start, int[] nums, int target) 
    { 
    1. if (start >= nums.length) return (target == 0);    
    2. if (groupSum1(start + 1, nums, target - nums[start])) return true;    
    3. if (groupSum1(start + 1, nums, target)) return true;    
    4. return false; 
    } 

這裏的執行（假設這是你所要求的）：

1 call groupSum1(0, {10, 8, 6}, 16) 
    1. 0 < 3 next 
2 call groupSum1(1, {10, 8, 6}, 6) 
    1. 1 < 3 next 
3 call groupSum1(2, {10, 8, 6}, -2) 
    1. 2 < 3 next 
4 call groupSum1(3, {10, 8, 6}, -8) 
    1. 3 == 3 return false to call 3  
back to call 3 in line 2. 
5 call groupSum1(3, {10, 8, 6}, -2) 
    1. 3 == 3 return false to call 3 
back to call 3 in line 3. 
    return false to call 2 
back to call 2 in line 2. 
6 call groupSum1(2, {10, 8, 6}, 6) 
    2 < 3 next 
7 call groupSum1(3, {10, 8, 6}, 0) 
    3 == 3 return true to call 6 
back to call 6 in line 2. 
    return true to call 2 
back to call 2 in line 3. 
    return true to call 1 
back to call 1 in line 2. 
    return true 

在遞歸調用前面的數字只是一個指標我用來跟蹤深度。我希望這是可以理解的。

Answer 2

將代碼視爲連續調用函數可能會有所幫助，直到它到達目標（或false）。 「最內層」呼叫的結果將返回true（或target == 0）。

有了，下面的條件會或不會被滿足：

if (groupSum1(start + 1, nums, target - nums[start])) return true;    
if (groupSum1(start + 1, nums, target)) return true;