Java回溯递归实现数组子集函数为何返回全空列表？

我编写了一个使用回溯与递归实现的函数，用于返回给定数组的子集列表，将该void类型函数命名为subset：

import java.util.ArrayList;
import java.util.List;
public class Main{
public static void main(String[] args) {
        ArrayList<Integer> nums = new ArrayList<>();
        List<List<Integer>> list= new ArrayList<>();
        int[] arr = {2,3,5};
        subset(list,nums,arr,0);  
        System.out.println(list);
    } 
static void subset(List<List<Integer>> list,
                   ArrayList<Integer> nums,
                   int[] arr, int index){
        if(index==arr.length){
            list.add(nums);
            return  ;
        }
        int c = arr[index];
        nums.add(c);
        subset(list,nums,arr,index+1);   
        nums.remove(nums.size()-1);
        subset(list,nums,arr, index+1);  
        return ;
    }
}

预期结果与实际输出：

output={[],[],[],[],[],[],[],[]}
expected={[2,3,5],[2,3],[2,5],[2],[3,5],[3],[5],[]}

问题原因 #

你向list中添加的是nums的对象引用，而非独立的列表副本。整个递归过程里，始终在操作同一个nums实例：每次递归返回后都会执行nums.remove(nums.size()-1)进行回溯，最终所有递归路径结束时，nums会被完全清空。因为list中存储的所有元素都是指向同一个nums的引用，所以输出时所有列表都会显示为空。

解决方案 #

当递归终止（index == arr.length）时，不要直接添加原nums对象，而是创建它的新副本存入list。通过new ArrayList<>(nums)可以生成一个与当前nums内容完全相同但独立的列表，后续的回溯操作不会影响已存入list的子集。

修改后的subset函数：

static void subset(List<List<Integer>> list,
                   ArrayList<Integer> nums,
                   int[] arr, int index){
    if(index == arr.length){
        list.add(new ArrayList<>(nums)); // 添加nums的副本而非引用
        return;
    }
    int c = arr[index];
    nums.add(c);
    subset(list, nums, arr, index+1);   
    nums.remove(nums.size()-1);
    subset(list, nums, arr, index+1);  
}

另外，原代码缺少import java.util.List;，补充后才能正常编译。修改后运行程序即可得到预期的子集结果。

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