本文详解如何用纯递归+回溯（无循环）生成整数数组的所有子集，并重点解决因对象引用导致的“全为空列表”经典错误。
本文详解如何用纯递归+回溯（无循环）生成整数数组的所有子集，并重点解决因对象引用导致的“全为空列表”经典错误。
在Java中，利用回溯（Backtracking）和递归生成一个数组的所有子集，是一种典型的组合问题解法。其核心思想是：对每个元素，做出「选」或「不选」两种决策，递归展开至数组末尾，每条递归路径终点即对应一个子集。
然而，初学者常陷入一个关键陷阱——误将同一 ArrayList 实例多次添加进结果列表。如原始代码所示：
list.add(nums); // ❌ 错误：添加的是引用，所有条目指向同一个对象
由于 nums 是全程复用的单一 ArrayList 对象，当回溯过程中反复 remove() 和后续递归执行完毕后，该列表最终为空；而 list 中存储的却是多个对该空列表的引用，因此输出为 [[],[],...,[]]。
✅ 正确做法是在递归到达边界（index == arr.length）时，创建 nums 的独立副本并加入结果：
立即学习“Java免费学习笔记（深入）”；
Alibabacloud Sdk Client Initialization For Java
下载
在 Java 中初始化和管理阿里云 SDK客户端。包括单例模式、线程安全、endpoint 与 region 配置、VPC 终端节点、同步与异步等。
list.add(new ArrayList<>(nums)); // ✅ 正确：深拷贝当前状态
new ArrayList(nums) 构造了一个新列表，包含 nums 当前所有元素的副本，与原列表内存隔离，确保每个子集独立持久化。
以下是完整、可运行的修正版代码（已适配标准Java泛型与命名规范）：
import java.util.*;
public class SubsetGenerator {
public static void main(String[] args) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> current = new ArrayList<>();
int[] arr = {2, 3, 5};
subset(result, current, arr, 0);
System.out.println(result);
// 输出: [[2, 3, 5], [2, 3], [2, 5], [2], [3, 5], [3], [5], []]
}
private static void subset(List<List<Integer>> result,
List<Integer> current,
int[] arr, int index) {
// 递归终止条件：已遍历完所有元素
if (index == arr.length) {
result.add(new ArrayList<>(current)); // 关键：保存当前路径快照
return;
}
// 选择当前元素
current.add(arr[index]);
subset(result, current, arr, index + 1);
// 回溯：撤销选择
current.remove(current.size() - 1);
// 不选择当前元素（隐式跳过，直接递归下一位置）
subset(result, current, arr, index + 1);
}
}? 注意事项与最佳实践：
-
避免原始类型数组直接传参修改：本例中
arr仅读取，安全；若需动态修改，建议封装为不可变结构或额外保护。 -
泛型一致性：参数类型统一使用
List<integer></integer>而非具体实现类（如ArrayList），提升扩展性与可测试性。 - 空间优化提示：该算法时间复杂度为 O(2ⁿ)，空间复杂度为 O(n)（递归栈深度 + 单个子集最大长度），符合子集问题理论下界。
-
扩展性思考：若需去重子集（处理含重复元素数组），可在递归前对
arr排序，并在subset()中跳过相邻相同值（即if (index > 0 && arr[index] == arr[index-1]) continue;），但需配合更精细的剪枝逻辑。
掌握这一模式，不仅适用于子集生成，更是理解回溯算法本质（决策树遍历 + 状态快照 + 撤销机制）的重要基石。
