Java回溯/递归求数组子集：为何直接操作原列表失效？

你尝试用递归回溯法生成字符数组的所有子集，以下是可正常运行的代码：

public static void main(String[] args) {
    char[] s = {'a','b','c','d','e'};
    ArrayList<ArrayList<Character>> result= new ArrayList<ArrayList<Character>>();
    ArrayList<Character> t= new ArrayList<Character>();
    findSubsets(s,t,0,result);
}
static void findSubsets(char[] s,ArrayList<Character> t,int i,ArrayList<ArrayList<Character>> result) {
    if(i >= s.length) {
        if(t.size()>0) {
            result.add(t);
            printArrayListOfArrayList(result);
        }
        return;
    }
    findSubsets(s,t,i+1,result);
    ArrayList<Character> tmp1 = new ArrayList<>(t);  
    tmp1.add(s[i]); 
    findSubsets(s,tmp1,i+1,result);
}

而以下写法无法正常运行：

findSubsets(s,t,i+1,result);
t.add(s[i]); 
findSubsets(s,tmp1,i+1,result);

两种写法的核心差异原因 #

1. Java列表是引用类型，直接操作会污染递归状态 #

直接对原列表t执行add操作时，会破坏递归过程中的状态一致性：

• 递归调用传递的是t的引用，所有分支共享同一个列表对象。
• 当你在当前层执行t.add(s[i])后，这个修改会同步影响所有持有该引用的地方——包括之前递归分支中已经添加到result里的t，最终导致result中的所有子集被后续操作篡改，无法得到正确的独立子集。

2. 新列表拷贝实现状态隔离 #

创建新列表tmp1 = new ArrayList<>(t)时，会基于原t的内容生成一个独立的新列表对象：

• 后续对tmp1的添加操作只会影响这个新对象，不会干扰原t和其他递归分支的列表状态。
• 每个递归分支都持有自己独立的子集快照，确保所有生成的子集互不干扰，最终能正确收集到所有可能的子集。

另外补充：你提供的错误代码还存在语法问题——调用findSubsets(s,tmp1,i+1,result)时，tmp1并未定义，这也是代码无法运行的直接原因之一，但核心逻辑错误还是引用共享导致的状态污染。

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