引言

相信很多同学在学习回溯算法的时候经常会遇到一个困惑，为什么保留路径时要重新new一个子集呢？下面的代码是回溯算法中的一个经典问题——组合总和，不难发现在dfs函数中，保留路径时ans.add(new ArrayList<Integer>(combine));采用了这一一行代码，那么为什么ans.add(combine)是错误的呢？


class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> combine = new ArrayList<Integer>();
        dfs(candidates, target, ans, combine, 0);
        return ans;
    }

    public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {
        if (idx == candidates.length) {
            return;
        }
        if (target == 0) {
            ans.add(new ArrayList<Integer>(combine));
            return;
        }
        // 直接跳过
        dfs(candidates, target, ans, combine, idx + 1);
        // 选择当前数
        if (target - candidates[idx] >= 0) {
            combine.add(candidates[idx]);
            dfs(candidates, target - candidates[idx], ans, combine, idx);
            combine.remove(combine.size() - 1);
        }
    }
}

这其中就和Java的参数传递方式有关。本文便来介绍Java到底是值传递还是引用传递？

参数传递方式：
值传递：指的是在方法调用时，传递的是参数是按值的拷贝传递。
引用传递：指的是在方法调用时，传递的参数是按引用进行传递，其实传递的是引用的地址，也就是变量所对应的内存空间的地址。

由于combine是ArrayList的实例，并且它是引用类型的对象，在参数传递时

正文

在使用Java语言的过程中，参数传递无处不在，但总归会遇到三类情况：基本数据类型、引用类型以及String，本文对这三种情况进行对比，并从中考察Java的参数传递方式。

案例一：int传递

public class PassedByValue {
    
    public static void main(String[] args) {
        int a = 1;
        test1(a);
        System.out.println(a);
    }

    public static void test1(int a) {
        a++;
        System.out.println(a);
    }
    
}

运行结果为：
2
1

这一案例中，传入的参数a原值并未发生改变，改变的仅是方法体内的参数a，符合值传递的特征。

案例二：ArrayList传递

public class PassedByValue {

    public static void main(String[] args) {
        List<Integer> arrays1 = new ArrayList<>();
        test2(arrays1);
    }

    public static void test2(List<Integer> arrays1) {
        arrays1.add(1);
        System.out.println(arrays1);
    }
    
}

运行结果：
[1]
[1]

这一案例中，传入的参数arrays1原值发生了改变，符合引用传递的特征。

案例三：String类型传递

public class PassedByValue {

    public static void main(String[] args) {
        String s = "b";
        test3(s);
        System.out.println(s);
    }
    
    public static void test3(String s) {
        s += "a";
        System.out.println(s);
    }
    
}

运行结果：
ba
b

这一案例中，传入的参数s原值未发生改变，符合值传递的特征。

看完这三个案例，很多同学是不是心里会想，Java其实同时存在值传递和引用传递。这样理解一定程度上没有问题，但更合理的解释为：Java中只存在值传递。案例一为基本数据类型，其参数拷贝不影响原值，这不难理解；案例二为引用类型，其参数拷贝发生改变，本质上是引用地址发生了改变，因此也影响了原值；案例三为String类型，其参数拷贝未发生改变，但其本身是一个类对象，这是因为它的char型数组增加了final关键字，因此不可变，所以在方法体内对其进行赋值不会改变原值。

看到这里，文章开头的问题想必同学们也能够想清楚了，重新new一个List的原因便在于，combine随着递归运行会发生改变，如果不在保留路径时重新创建一个实例对象，而是直接将引用存入res列表，那么最后res中的子集会随之改变，从而产生错误。