Java中递归生成子集时ArrayList引用陷阱与深拷贝解决方案

花韻仙語 2025-12-27 00:00:00 次阅读

本文解析为何递归生成幂集时全局列表只保存空数组——根本原因在于java中对象引用的传递机制导致所有添加到结果集的都是同一array

list实例的引用，需在每次添加前创建新副本。

在Java中，所有非基本类型（如ArrayList）的变量本质上都是引用（即“指向堆内存中对象的指针”），而方法参数传递始终是“按值传递”，只不过这个“值”本身是一个引用副本。这意味着：

✅ 调用 .add()、.remove() 等方法会修改原对象（因为副本引用指向同一堆内存）；
❌ 但执行 ans = new ArrayList() 或 ans.clear() 后再传参，不会影响调用方持有的旧引用。

回到你的代码问题：

pow.add(ans); // ❌ 错误：反复添加的是同一个 ans 引用！

虽然 System.out.println(ans) 在递归终止时显示了正确的子集内容，但 pow 中存储的全部是同一个 ans 对象的引用。当递归回溯执行 ans.remove(...) 时，它持续修改这个唯一实例——最终 ans 变为空，而 pow 中所有元素都指向这个已被清空的对象，因此 System.out.println(pow) 输出 [[], [], [], ...]。

✅ 正确做法：每次将当前状态快照加入 pow 时，必须创建独立的新列表副本：

private static void powset(int[] arr, int i, ArrayList ans) {
    if (i >= arr.length) {
        System.out.println(ans);
        pow.add(new ArrayList<>(ans)); // ✅ 关键修复：深拷贝当前状态
        return;
    }
    ans.add(arr[i]);
    powset(arr, i + 1, ans);
    ans.remove(ans.size() - 1);
    powset(arr, i + 1, ans);
}