如何獲得遞歸算法以在運行完成之前返回值？

Question

我有下面的算法，其目標是找到一系列數字的所有可能的排列，因爲它們可以切換符號。當它到達樹中的一個葉節點時，它將調用另一個遍歷列表的方法來查看該排列的和是否等於該系列中的一個數。我也在用算法來弄清楚一個系列的子集是否少於給定的數字。例如60,35和40，數字60 + 40 < 110.我的問題是，一旦發現樹中的一個分支是我需要的，其他分支仍將被探索。我怎麼能打斷這件事？現在我只有一個system.exit(1);

public static int PlusMinus(Node start, Node node, int Sum){ 
    Node head = start; 
    boolean Success = false; 
    if(node != null){ 
     PlusMinus(head, node.next, node.item+Sum); 
     PlusMinus(head, node.next, node.item*(-1)+Sum); 
     return Sum; 
    } 

    else{ 
     Success = getSum(Sum,start); 
     if(Success == true){ 
      System.out.println("Yes"); 
      System.exit(1); 
      return 1; 
     } 
    } 
    return 0; 
} 

在上面看，我的初衷是有它的葉節點和返回給調用程序。正如我通過程序逐步瞭解的那樣，如果最右邊的分支是正確的排列，它不會僅止於葉節點返回值。它仍然會跳回到父級，然後繼續測試下一個分支。

Answer 1

你的返回值應該是一個布爾值，表示你是否找到了你正在尋找的總和。由於您沒有使用您的方法返回的當前值，因此您看起來並不需要它。

public static boolean PlusMinus(Node start, Node node, int Sum){ 
    Node head = start; 
    if(node != null) { 
     // you should return true if either of the recursive calls returned true 
     if (PlusMinus(head, node.next, node.item+Sum)) 
      return true; 
     return PlusMinus(head, node.next, node.item*(-1)+Sum); 
    } else { 
     return getSum(Sum,start); 
    } 
} 

編輯：

我不知道你的getSum方法做什麼，但它看起來像你不需要它。您應該傳遞給下一個遞歸調用Sum-node.item或Sum+node.item，具體取決於當前節點應該參與總和的符號，並檢查當您到達葉節點時是否達到0。

public static boolean PlusMinus(Node start, Node node, int Sum){ 
    if(node != null) { 
     // you should return true if either of the recursive calls returned true 
     if (PlusMinus(head, node.next, Sum - node.item)) 
      return true; 
     return PlusMinus(head, node.next, Sum + node.item); 
    } else { 
     return Sum == 0; 
    } 
}