递归子集生成代码差异解析：为何需用new ArrayList包裹state？

两段代码的核心行为差异 #

• 直接添加state的代码：最终返回的output是全空的列表集合，所有元素均为空数组。
• 用new ArrayList<Integer>(state)包裹后添加的代码：能正确返回数组的所有有效子集。

底层原理差异 #

Java中对象引用与对象实体是分离的：state只是指向一个ArrayList对象的引用，而非对象本身。

直接添加state的问题 #

每次执行output.add(state)，都是把同一个state引用存入output集合。而回溯过程中，我们会反复对state执行add和remove操作（这是回溯复用容器的核心逻辑）。当整个递归回溯完成后，state会回到初始的空状态——此时output里的所有元素都是指向这个空列表的引用，所以最终看到的就是全空的集合。

用new ArrayList<>(state)包裹的作用 #

new ArrayList<>(state)会创建一个全新的ArrayList对象，并把当前state中的所有元素拷贝到这个新对象里。此时存入output的是这个新对象的引用，和原state的引用完全独立。后续对原state的修改（add/remove）不会影响这个新对象的内容，这样就能把递归过程中每个分支的状态快照永久保存下来，最终得到所有有效子集。

为什么必须进行包裹操作 #

回溯算法的核心是复用同一个状态容器来遍历所有可能的子集分支，避免频繁创建对象带来的性能开销。但如果不通过new ArrayList<>(state)创建新对象，结果集里保存的都是同一个容器的引用，最终容器会回溯到初始空状态，导致所有结果都变成空列表。只有创建新对象保存当前状态的拷贝，才能让每个分支的子集状态被独立留存，得到正确的结果。

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