LeetCode组合总和问题：递归中为何不能直接添加ArrayList到结果？

问题场景 #

我正在解决LeetCode上的「组合总和」问题，题目要求如下：

给定一组不同的整数candidates和一个目标整数target，返回所有候选数的唯一组合，使所选数字的和等于target，组合可按任意顺序返回。同一数字可从candidates中无限制选取，两个组合的区别在于至少一个数字的出现频率不同。

我写出了如下解决方案：

class Solution {
    public void recUtil(List<List<Integer>> result, int[] candidates, List<Integer> list, int sum, int target, int ind) {
        if(sum>target || ind>=candidates.length) return;
        if(sum==target) {
            result.add(new ArrayList<>(list));
            return;
        }

        recUtil(result, candidates, list, sum, target, ind+1);
        list.add(candidates[ind]);
        recUtil(result, candidates, list, sum+candidates[ind], target, ind);
        list.remove(list.size()-1);
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        
        recUtil(result, candidates, new ArrayList<>(), 0, target, 0);

        return result;        
    }
}

但当我将第5行的result.add(new ArrayList<>(list));替换为result.add(list);时，程序无法正常工作。输入为[2,3,6,7]、目标值7时，结果ArrayList中得到两个空列表[[],[]]，而非预期的[[2,2,3],[7]]。

原因解释 #

这是Java中引用类型的特性导致的：

• List是引用类型，当你执行result.add(list)时，并没有把list中的元素复制一份存入结果集，而是把这个list对象的内存引用存进了result。也就是说，result里的所有元素都指向同一个List对象。
• 你的递归过程用到了回溯：每次递归调用后会执行list.remove(list.size()-1)，把之前添加的元素移除，让list回到调用前的状态，继续探索其他分支。
• 当整个递归结束时，这个唯一的List对象已经被回溯操作清空了，所以result里的两个元素（其实是同一个引用）指向的都是空列表，最终输出[[],[]]。
• 而result.add(new ArrayList<>(list))是创建了一个全新的ArrayList对象，并把当前list中的所有元素复制到新列表里。这个新列表和原list是完全独立的，后续原list的回溯修改不会影响它，所以能正确保存找到的组合状态。

内容的提问来源于stack exchange，提问作者Harshith Pillai