Return 使用递归时根节点的路径

Question

我正在尝试为 subset-sum problem. I have created a function inspired by 创建一个递归函数。

问题：我正在尝试从某个数组（例如 [50,40,30,20]）中选取一些元素，其总和是我定义为 sum（例如 100）的某个值。

我按照该回答中的建议创建了稍微修改过的函数。

从前面拿起并select是否编辑它select编辑它。

如果我 select 一个元素，则简化列表的总和将小于 select 元素，否则如果我不 select 该元素，则来自缩减后的名单将是原来的名单。

但是，我发现最困难的事情是 return追踪到递归调用的根节点的路径。当我到达总和匹配的节点时，我能够打印路径。

这是我的函数：

private static boolean findSumFromSubList(ArrayList<Integer> set, Integer sum, ArrayList<Integer> result) {

    if (sum < 0)
        return false;

    if (sum == 0) {
        // Got it! Awesome! Print it!
        System.out.println(result);
        return true;
    }

    if (set.size() == 0 && sum != 0)
        return false;

    ArrayList<Integer> newSet = new ArrayList<>(set);
    newSet.remove(0);

    System.out.println("Left: Picking up " + set.get(0));
    result.add(set.get(0));
    if (findSumFromSubList(newSet, sum - set.get(0), new ArrayList<>(result))) {
        return true;
    }

    System.out.println("Right: NOT Picking up " + set.get(0));
    result.remove(result.size()-1);
    if (findSumFromSubList(newSet, sum, new ArrayList<>(result))) {
        return true;
    }

    return false;
}

我是这样称呼它的：

    ArrayList<Integer> pair = new ArrayList<>();
    pair.add(50);
    pair.add(40);
    pair.add(30);
    pair.add(20);
    ArrayList<Integer> result = new ArrayList<>();
    boolean resultBool = findSumFromSubList(pair, 100, result);

    System.out.println("bool: " + resultBool + ", result: " + result);

我得到的输出是：

Left: Picking up 50
Left: Picking up 40
Left: Picking up 30
Right: NOT Picking up 30
Left: Picking up 20
Right: NOT Picking up 20
Right: NOT Picking up 40
Left: Picking up 30
Left: Picking up 20
[50, 30, 20]
bool: true, result: [50]

所以我能够在递归中获得输出，但我如何才能 return 将那个值传递给根调用函数。因为resultreturns 50而已。

Answer 1

与其复制 result，不如尝试传递它，以便在递归时对其进行修改。

private static boolean getSum(ArrayList<Integer> set, Integer sum, LinkedList<Integer> result) {
    // ...

    System.out.println("Left: Picking up " + set.get(0));
    result.add(set.get(0));
    if (getSum(newSet, sum - set.get(0), result)) {
        return true;
    }
    result.removeLast();

    System.out.println("Right: NOT Picking up " + set.get(0));
    if (getSum(newSet, sum, result)) {
        return true;
    }
}

您可以将类似的逻辑应用于 set，但我会将其作为练习留给 reader。

Return 使用递归时根节点的路径

Return Path at the root node when using recursion

java

recursion

tail-recursion