Java - SubSet递归和递归绘图

Question

我在理解代码的递归时遇到了问题，我试着画我的树跟随，但有些东西我半路上不清楚。谁能帮我理解代码片段，并在页面上绘制，或绘画或任何其他软件，递归树，让我可以完全理解代码。

为什么会有两个递归？我不明白第二个递归是如何工作的(在||之后)。

​

​

public static boolean hasSum(int[] array, int start, int sum) {
    if (sum == 0)
        return true;

    if (start > array.length - 1)
        return false;

    return hasSum(array, start + 1, sum - array[start])
            || hasSum(array, start + 1, sum);

}

非常感谢您的帮助

Answer 1

搜索的子集和(即sum)可以包括当前元素(array[start]) 或不包括当前元素的(因此||)。

如果它包含array[start]，我们应该找到从索引start+1开始的子数组的一个子集，它的和是sum - array[start]。

这是由hasSum(array, start + 1, sum - array[start])处理的。

如果它不包括array[start]，我们应该找到从索引start+1开始的子数组的一个子集，它的和是sum (即，由于当前元素不参与和，我们必须在更小的数组中找到相同的和)。

这是由hasSum(array, start + 1, sum)处理的。

因此出现了两个递归调用。