如何获得递归算法以在运行完成之前返回值？

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; 
    } 
}