LeetCode 78. 子集

题目描述
给定一个整数数组 nums，数组中的元素互不相同。要求返回该数组所有可能的子集（幂集）。解集不能包含重复的子集，可以按任意顺序返回。

示例
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

解题过程循序渐进讲解

第一步：理解问题与目标
子集是指从原数组中选取任意个（包括0个和全部）元素组成的集合。由于元素互不相同，我们不需要考虑去重（如 [1,2] 和 [2,1] 视为同一个子集，通常按原数组顺序输出即可）。目标是枚举所有可能的子集，总数为 \(2^n\) 个（n为数组长度）。

第二步：初步思考枚举方法
最直接的思路是递归回溯：

• 从第一个元素开始，每个元素有两种选择：选或不选。
• 按顺序考虑每个元素，做出选择，直到处理完所有元素，就得到一个子集。
• 记录所有过程中生成的子集。

第三步：设计递归函数
定义递归函数 backtrack(start, path)：

• start 表示当前要考虑的元素下标。
• path 是当前已选择的元素列表（即当前子集）。
  每次递归时：

1. 将当前的 path 加入结果集（因为每一步都代表一个子集）。
2. 从 start 开始遍历剩余元素：
   • 将当前元素加入 path。
   • 递归处理下一个位置（start + 1）。
   • 回溯：将当前元素从 path 中移除，尝试不选它的分支（实际上通过循环遍历下一个元素实现）。

第四步：举例推演
以 nums = [1,2,3] 为例，递归树如下：

初始: path=[]
1. 加入[]到结果
2. 选1: path=[1]
   加入[1]到结果
   选2: path=[1,2]
       加入[1,2]到结果
       选3: path=[1,2,3] → 加入结果
       回溯，尝试不选3（已循环完）
   回溯，尝试不选2，选3: path=[1,3] → 加入结果
3. 回溯，尝试不选1，选2: path=[2]
   加入[2]到结果
   选3: path=[2,3] → 加入结果
4. 回溯，尝试不选2，选3: path=[3] → 加入结果

最终得到所有8个子集。

第五步：代码实现要点

• 结果集 result 初始化为空列表。
• 递归函数内部先添加当前 path 的副本（否则后续修改会影响已保存的结果）。
• 遍历从 start 到 n-1 的元素，依次选择、递归、回溯。
• 时间复杂度：\(O(n \cdot 2^n)\)，因为生成 \(2^n\) 个子集，每个子集平均长度 \(n/2\)。空间复杂度：\(O(n)\) 递归栈深度。

第六步：扩展思路（位运算解法）
另一种常见方法是利用二进制位表示每个元素是否被选中：

• 子集总数 \(2^n\) 对应从 0 到 \(2^n-1\) 的二进制数。
• 每个二进制数的第 i 位为1表示选中 nums[i]。
• 例如 nums=[1,2,3]，二进制 101 表示子集 [1,3]。
• 遍历所有二进制数，构造对应子集即可。这种方法同样高效，且易于理解。

总结
本题是回溯算法的经典应用，通过递归枚举所有选择组合，关键点在于：

1. 每个元素有选/不选两种状态。
2. 递归时记录当前路径，并在每一步保存路径副本到结果。
3. 注意避免重复（本题因元素互异，自然保证唯一）。
   通过这个例子，可以深入理解如何系统地枚举组合问题。