如何让递归算法在运行结束前返回值

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