day153—回溯—子集（LeetCode-78）

题目描述

给你一个整数数组nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按任意顺序返回解集。

示例 1：

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

示例 2：

输入：nums = [0]输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums中的所有元素互不相同

解决方案：

这段代码的核心功能是生成一个数组的所有子集（包括空集和数组本身），采用「回溯 + 递归」的思路实现，只是把 “先不选、后选” 的顺序换成了 “先选、后不选”，最终效果完全一致。下面用简洁的语言解释整体逻辑：

核心逻辑

1. 成员变量作用：

   • t：临时数组，用于存储当前正在构造的子集（相当于 “路径”）；
   • ans：最终结果数组，存储所有生成的子集。

2. 递归函数dfs逻辑：

   • 参数curr：表示当前处理到数组nums的第curr个元素；
   • 终止条件：当curr == nums.size()时，说明所有元素都处理完毕，此时t就是一个完整的子集，将其加入ans后返回；
   • 核心流程（先选后不选）：①选当前元素：把nums[curr]加入临时数组t，递归处理下一个元素（curr+1）；递归返回后，执行t.pop_back()恢复现场（删掉刚加入的元素，避免影响后续选择）；②不选当前元素：直接递归处理下一个元素（curr+1），不对t做任何修改。

3. 主函数subsets：

   • 从第 0 个元素开始调用dfs，启动递归过程；
   • 最终返回存储了所有子集的ans。

关键特点

• 逻辑等价性：和你之前看到的 “先不选、后选” 版本功能完全一致，只是选择顺序相反，最终生成的子集顺序会略有不同（比如nums=[1,2]会生成[[1,2],[1],[2],[]]，而非[[],[2],[1],[1,2]]），但都是完整的子集集合；
• 核心思想：通过 “选（修改t后递归）+ 不选（直接递归）” 的组合，遍历所有可能的元素组合，pop_back是回溯的关键，用于恢复临时数组的状态，保证不同选择分支互不干扰。

总结

1. 核心思路：递归遍历每个元素，对每个元素执行 “选（加入临时数组）→ 递归 → 恢复 → 不选（直接递归）” 的操作；
2. 关键操作：t.push_back()（选元素）和t.pop_back()（恢复现场）是实现回溯的核心；
3. 最终效果：通过递归覆盖所有元素的 “选 / 不选” 组合，最终收集到数组的全部子集。

函数源码：

class Solution { public: vector<int> t; vector<vector<int>> ans; void dfs(int curr,vector<int>& nums){ if(curr==nums.size()){ ans.push_back(t); return ; } t.push_back(nums[curr]); dfs(curr+1,nums); t.pop_back(); dfs(curr+1,nums); } vector<vector<int>> subsets(vector<int>& nums) { dfs(0,nums); return ans; } };