为何下述求数组所有子集的代码中，ArrayList lt执行后为空？

问题描述 #

需求是返回数组的所有子集并存储在列表中，但执行下述代码后，列表lt始终为空，预期lt应存储所有子集，请问问题原因是什么？

问题代码 #

class Solution {
    public void sub(int idx,int[] nums,List<Integer> arr,ArrayList<List<Integer>> lt){
        if(idx>=nums.length){
            lt.add(arr);
            // System.out.println(arr.toString());
            return;
        }
        arr.add(nums[idx]);
        sub(idx+1,nums,arr,lt);
        arr.remove(arr.size()-1);
        sub(idx+1,nums,arr,lt);
    }

    public List<List<Integer>> subsets(int[] nums) {
        List<Integer> arr=new ArrayList<>();
        ArrayList<List<Integer>> lt=new ArrayList<List<Integer>>();
        sub(0,nums,arr,lt);
        return lt;
    }
}

问题原因 #

• Java中对象采用引用传递，你在递归全程复用同一个ArrayList对象arr，调用lt.add(arr)时只是把arr的引用存入列表，而非当前arr状态的副本。
• 递归回溯阶段的arr.remove(arr.size()-1)操作会修改这个唯一的arr对象，包括已经存入lt的引用所指向的内容。
• 当整个递归流程结束后，arr会被回溯到初始的空状态，导致lt中所有元素最终都指向这个空对象，看起来就像lt是空的（实际是所有子集都变成了空列表）。

修复方法 #

在将arr添加到lt时，创建一个新的ArrayList来保存当前arr的内容，避免直接传递原引用：

if(idx>=nums.length){
    lt.add(new ArrayList<>(arr)); // 创建当前状态的副本添加
    return;
}

这样每次存入lt的都是独立的列表对象，后续对原arr的修改不会影响已经保存的子集。

内容的提问来源于stack exchange，提问作者Paurab Bhattacharjee