在Java里用递归配合回溯法生成集合的所有子集，是非常经典的算法练习。很多人在写代码时会定义一个全局的结果列表，在递归过程中把临时组合加进去，但运行后发现最终结果里的每个子集都一模一样，或者全是空列表。这种现象并不是逻辑写错，而是对ArrayList的引用机制理解不够导致的。Java中对象类型的变量保存的是堆内存地址，当你把同一个temp列表多次加入结果集时，实际上加进去的是同一个对象的引用，后续对temp的修改会反映到已经加入的所有元素上。
引用陷阱产生的底层原因
要弄清楚为什么递归生成子集会出问题，必须先理解ArrayList在内存中的表达方式。当我们声明一个ArrayList对象并把它作为参数传递给方法，或者把它存入另一个List中，存储的并不是这份数据的拷贝，而是指向堆中实际数组结构的引用。在回溯算法中，通常有一个临时的List叫作temp，用来保存当前路径上的元素。每次递归回到上一层之前，我们会执行temp.remove(temp.size()-1)来撤销选择，这个操作直接修改了temp指向的那个对象。
如果我们在递归的终止条件处直接写result.add(temp)，那么result里面保存的全都是同一个temp对象的引用。等到整个递归结束，temp因为回溯操作变成了空列表，你从result里取出来的每一个元素也就都成了空列表。即便temp最后不是空，所有结果也会是temp最后一轮的值。这种陷阱在嵌套结构或者多次添加时尤其隐蔽，因为代码逻辑看起来完全没有问题，但输出就是不对。
下面这段示例代码就展示了典型的错误写法，注意看add这一行，它并没有创建新对象：
import java.util.ArrayList;
import java.util.List;
public class SubsetWrong {
static List<List<Integer>> result = new ArrayList<>();
public static void backtrack(List<Integer> nums, List<Integer> temp, int start) {
// 错误：直接添加引用
result.add(temp);
for (int i = start; i < nums.size(); i++) {
temp.add(nums.get(i));
backtrack(nums, temp, i + 1);
temp.remove(temp.size() - 1);
}
}
public static void main(String[] args) {
List<Integer> nums = List.of(1, 2, 3);
backtrack(new ArrayList<>(nums), new ArrayList<>(), 0);
System.out.println(result);
}
}
使用构造函数实现浅层深拷贝
解决上述引用陷阱最直接的方式，是在把临时列表加入结果集的时候，创建一个新的ArrayList对象，把当前temp里的内容复制过去。Java的ArrayList提供了一个接受Collection参数的构造函数，也就是new ArrayList<>(temp)，它会遍历temp里的元素并放到一个新的列表对象中。由于Integer是不可变类，对于纯Integer或String这类不可变元素的子集来说，这种写法已经足够安全，相当于做了一次深拷贝。
修正后的代码只需要在添加那一行改动即可，其余回溯逻辑保持不变。这样每一次递归出口处加入result的，都是一个独立的列表实例，之后对temp的remove操作不会再影响已经保存的结果。这种方式开销小、代码清晰，也是LeetCode等平台上最常被推荐的写法。不过要注意，如果temp里面装的是自定义的可变对象，比如你自己的Node类，那么new ArrayList<>(temp)只是复制了引用，对象本身还是同一份，这时就需要更深一层的拷贝。
以下是正确的添加方式示例，注意对比上一节的差别：
import java.util.ArrayList;
import java.util.List;
public class SubsetRight {
static List<List<Integer>> result = new ArrayList<>();
public static void backtrack(List<Integer> nums, List<Integer> temp, int start) {
// 正确：使用构造函数创建独立副本
result.add(new ArrayList<>(temp));
for (int i = start; i < nums.size(); i++) {
temp.add(nums.get(i));
backtrack(nums, temp, i + 1);
temp.remove(temp.size() - 1);
}
}
public static void main(String[] args) {
List<Integer> nums = List.of(1, 2, 3);
backtrack(new ArrayList<>(nums), new ArrayList<>(), 0);
System.out.println(result);
}
}
嵌套对象场景下的深拷贝方案
当子集中的元素不是不可变类型，而是包含可变属性的自定义对象，浅层复制就无法满足需求。例如temp中存放的是ArrayList<ArrayList<Integer>>，或者你自己的class User带有name和age字段，此时new ArrayList只能保证外层列表独立，内层的对象依然共享。修改其中一个子集里的内层对象，另一个子集也会跟着变。要彻底隔离，必须实现深拷贝。
一种简单的深拷贝思路是递归复制：如果元素是List，就再new一个ArrayList并把里面的基本类型加进去；如果元素是自定义对象，就调用它的拷贝构造或者clone方法生成新实例。另一种在工程里常用的办法是利用序列化，把对象写到字节流再读回来，这样得到的一定是不带任何共享引用的全新对象，但要求所有涉及的对象都实现Serializable接口，且性能比手动复制差一些。对于算法题中的子集生成，通常不需要走到序列化这一步，手动逐层new就已经够用。
下面给出一个处理嵌套列表的深拷贝辅助方法示例，你可以根据需要在递归出口调用它：
import java.util.ArrayList;
import java.util.List;
public class DeepCopyUtil {
// 对List<List<Integer>>做深拷贝
public static List<List<Integer>> deepCopy(List<List<Integer>> source) {
List<List<Integer>> copy = new ArrayList<>();
for (List<Integer> inner : source) {
copy.add(new ArrayList<>(inner));
}
return copy;
}
public static void main(String[] args) {
List<List<Integer>> temp = new ArrayList<>();
temp.add(new ArrayList<>(List.of(1, 2)));
List<List<Integer>> result = deepCopy(temp);
temp.get(0).set(0, 99);
System.out.println(result); // 输出[1, 2]，不受修改影响
}
}
除了上述方式，还可以让自定义类实现Cloneable接口并重写clone方法，在方法内部对字段逐一复制。如果字段里还有引用类型，就要继续调用它们的clone，形成链条。虽然写起来繁琐，但能在编译期就明确拷贝边界，比序列化更容易排查问题。在写递归生成子集的程序时，先想清楚你的元素是不是不可变，再决定用new ArrayList还是手写深拷贝，基本就能避开所有引用陷阱。
Java递归ArrayList引用陷阱深拷贝修改时间：2026-08-15 16:54:31