Java 递归通过 ArrayList 中的引用传递

Question

我正在研究一个问题，找出给定列表中所有整数组合的总和可以达到给定数字。

public class SumProblem {

/*
 * Input 2-2-3-7
 * Output 2+2+3 and 7
 */

public static ArrayList<ArrayList<Integer>>  find(ArrayList<Integer> input, int requiredSum) {
    ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    find(result, requiredSum, 0, new ArrayList<>(), 0, input);
    return result;
}

public static void find(ArrayList<ArrayList<Integer>> result , int requiredSum , int currentSum,  ArrayList<Integer> partialResult, int i, ArrayList<Integer> input) {

    if (currentSum == requiredSum ) {
        ArrayList<Integer> temp = new ArrayList<>();
        temp = (ArrayList<Integer>) partialResult.clone();
        result.add(temp);
        return;
    }

    if (i >= input.size()) {
        return;
    }
    find(result, requiredSum, currentSum , partialResult, i +1, input );
    partialResult.add(input.get(i));
    find(result, requiredSum, currentSum + input.get(i) , partialResult, i +1, input );
}

public static void main(String[] args) {

    ArrayList<Integer> input = new ArrayList<>();
    input.add(2);
    input.add(1);
    input.add(3);
    ArrayList<ArrayList<Integer>>  output = find(input, 3);
    System.out.println(output.toString());
}

我在下面写了代码。我面临一个问题。在下面的代码行中，即使我创建了新的 ArrayList 对象并将其分配给 partialResult，它也会将我遍历的所有数字相加。

partialResult.add(input.get(i));

谁能提出解决方案？

Answer 1

在这个问题的动态规划解决方案中，您有两个递归调用。一个应该不在结果中包含当前值，另一个包含。

您需要制作 partialResult 的防御性副本，否则两个递归调用都将引用相同 列表。列表是可变对象。如果两个调用都获得对同一个列表对象的引用，那么当您向它添加内容时任何地方，它们都将看到修改后的列表。

制作列表防御副本的最简单方法就是编写:

new ArrayList<>(partialResult)

这是程序的工作版本:

导入 java.util.*;

public class SumProblem {
    public static List<List<Integer>> find(List<Integer> input, int requiredSum) {
        List<List<Integer>> result = new ArrayList<>();
        find(result, requiredSum, 0, new ArrayList<>(), 0, input);
        return result;
    }

    public static void find(List<List<Integer>> result, int requiredSum, int currentSum,
            List<Integer> partialResult, int i, List<Integer> input) {
        if (currentSum == requiredSum) {
            result.add(new ArrayList<>(partialResult)); // add a copy of the list
            return;
        }

        if (i >= input.size()) {
            return;
        }
        // make defensive copies in the recursive calls
        find(result, requiredSum, currentSum, new ArrayList<>(partialResult), i + 1, input);
        partialResult.add(input.get(i));
        find(result, requiredSum, currentSum + input.get(i), new ArrayList<>(partialResult), i + 1, input);
    }

    public static void main(String[] args) {
        List<Integer> input = List.of(2, 8, 2, 3, 4);
        List<List<Integer>> output = find(input, 7);
        System.out.println(output);
    }
}

输出:

[[3, 4], [2, 2, 3]]

我做了一些其他的改变:

• 使用List<Integer>和 List<List<Integer>>作为类型(接口(interface)代码)
• 使用List.of()创建输入列表(在 Java 9 中添加)
• 不要调用 toString()在传递给 println 的对象上— 不需要