Java List 与地址相关的一点坑

Java 踩坑系列 （一）List

踩坑过程

今天刷回溯法 leetcode-77-组合 的时候。

因为返回值是 List<List<Integer>>，所以可以使用一个 List<Integer> 的对象来进行回溯。于是我想当然的写出了以下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
List<List<Integer>> ans = new ArrayList<List<Integer>>();

    private void backTracking(int start, int n, int k, List<Integer> temp) {
        if (temp.size() == k) { //当temp的size已经是k时，加入到ans中，退出
            ans.add(temp);
            return;
        }
        for (int i = start; i <= n; i++) { //因为不考虑重复的{「1，2」和「2，1」算重复，这里还没有剪枝
            temp.add(i);
            backTracking(i + 1, n, k, temp); //回溯
            temp.remove(temp.size() - 1); //回溯完，往上
        }
    }

    public List<List<Integer>> combine(int n, int k) {
        List<Integer> temp = new ArrayList<>(); //
        backTracking(1, n, k, temp);
        return ans;
    }

	 	public static void main(String[] args) {
        Solution solution = new Solution();
        List<List<Integer>> combine = solution.combine(4, 2);
        System.out.println(combine);
    }

结果运行的时候，出来的结果是这样的

[[], [], [], [], [], []]

原因

分析结果：返回值是规模是正确的，但是里面的值全都神秘消失了。

我调试了一遍程序，发现每一轮 temp 都被顺利加入到了 ans 中。但是当我对 temp 进行回溯时，会移除前一步中加入的元素，此时 ans 里加入的 temp 也发生了变化！实际上，在这段代码里 ans 中的每个子元素都指向 temp。因此当 temp 变化时，ans 里的每个元素也发生了变化。最后的回溯将 temp 清空了，所以也就出现了上面的情况。于是对代码稍做修改，答案就正确了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
List<List<Integer>> ans = new ArrayList<List<Integer>>();
private void backTracking(int start, int n, int k, List<Integer> temp) {
    if (temp.size() == k) { //当temp的size已经是k时，加入到ans中，退出
        List<Integer> cur = new ArrayList<>(temp);
        ans.add(cur);
        return;
    }
    for (int i = start; i <= n; i++) { //因为不考虑重复的{「1，2」和「2，1」算重复，这里还没有剪枝
        temp.add(i);
        backTracking(i + 1, n, k, temp); //回溯
        temp.remove(temp.size() - 1); //回溯完，往上
    }
}

public List<List<Integer>> combine(int n, int k) {
    List<Integer> temp = new ArrayList<>(); 
    backTracking(1, n, k, temp);
    return ans;
}

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

最后对第 8 行稍做修改，实现剪枝操作，就能较快的 AC 了

1
for (int i = start; i <= n - (k - temp.size()) + 1; i++) { //因为不考虑重复的{「1，2」和「2，1」算重复