Java Recursion - 几个递归调用的输出

Question

我的代码将生成 candidates 中值的所有组合(包括重复项)这样这些值将总结为目标。这是我对 https://leetcode.com/problems/combination-sum/ 的解决方案.

我对为什么需要包含以下代码行感到有点困惑:

currentSet = new ArrayList<>(currentSet);

这实际上将使 currentSet 成为所有递归调用的私有(private)变量。否则，currentSet 将是一个共享变量，递归调用将同时修改该变量，从而导致问题。例如，当代码中省略了上面的语句时， combinationSum({1, 2}, 4)具有以下输出:

[[1, 1, 2], [1, 1, 1, 1], [1, 2]]

数组 [1,2] 显然不等于 4。任何人都可以提供一个可靠的解释为什么会这样吗？

另外，我是否可以做任何优化，以便我的代码可以避免放入重复但重新排序的数组，因为我当前的暴力排序和检查 HashSet 中是否包含的方法会导致非常糟糕的复杂性。

public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Set<List<Integer>> returnSet = new HashSet<>();
        returnSet = combSum(candidates, target, 0, returnSet, new ArrayList<Integer>());
        return new ArrayList<>(returnSet);
    }

private Set<List<Integer>> combSum(int[] candidates, int target, int i, Set<List<Integer>> returnSet,
    List<Integer> currentSet) {
    currentSet = new ArrayList<>(currentSet);
    if(i == target) {
        Collections.sort(currentSet);
        if(!returnSet.contains(currentSet)) {
            returnSet.add(new ArrayList<Integer>(currentSet));
        }
    } else if(i <= target){
        System.out.println("Current set: " + returnSet.toString());
        System.out.println("Current sum: " + i + " current target: " + target);
        for(int a: candidates) {
            if(i + a <= target) {
                System.out.println("\tAdding: " + a + " so that the new sum will be: " + (i + a));
                currentSet.add(a);
                returnSet = combSum(candidates, target, i + a, returnSet, currentSet);
                currentSet.remove(currentSet.size() - 1);
            }
        }
    }

    return returnSet;
}

Answer 1

线

currentSet = new ArrayList<>(currentSet);

是调用复制构造函数的 Java 方式，即您正在创建新的 ArrayList，它最初包含旧列表中的所有元素。但是，原始列表和新列表是独立的，因此新列表中的任何更改都不会反射(reflect)到原始列表中。这在您的算法中很重要，因为这些行:

            currentSet.add(a);
            returnSet = combSum(candidates, target, i + a, returnSet, currentSet);
            currentSet.remove(currentSet.size() - 1);

在这里，您要在列表的末尾添加一个元素，找到所有可能的与该元素的递归组合，然后删除它以尝试使用另一个元素。如果您没有在递归调用中复制列表，currentSet 变量将被修改并且行

currentSet.remove(currentSet.size() - 1);

不会删除您在递归调用之前添加的元素，但会删除在递归中添加的其他一些元素 - 不要忘记您在递归中对元素进行排序，因此不会始终保留原始顺序。当您省略复制构造函数时，这就是您的示例中发生的情况。

可能的优化

我自然而然想到的是在开始时对候选项的初始数组进行排序，在combinationSum方法中。遍历排序的数组将避免重复，并且您不需要检查重复结果。