Leetcode 78. 子集

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

---

方法1：

创建返回二维数组 ans ，和临时存储信息的数组 path 。

进入到函数 dfs 中。如果 i==n ，则说明传进来的 nums 数组里的元素都已经递归完毕，则可以 return 。

回溯分为两种情况，选 或者 不选。

如果不选，就直接进入下一个递归（跳过这个元素）；如果选，则把他加入到临时存储信息的数组 path 中，然后进入下一个递归（决定后面的元素选不选），递归完毕后，要删除尾端元素，恢复现场（把这个递归周期中加进 path 中的删掉）。

代码：

class Solution {
public:vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> ans;// 创建返回数组ansvector<int> path;int n = nums.size();auto dfs = [&](auto&& dfs,int i)->void{if(i == n){ans.emplace_back(path);return ;}// 不选nums[i]dfs(dfs,i+1);// 选nums[i]path.emplace_back(nums[i]);// 把当前数字加入到path后dfs(dfs,i+1);path.pop_back();// 尾端删除元素，恢复现场};dfs(dfs,0);// 入口return ans;}
};

时间复杂度：O(n2ⁿ)。

其中 n 为 nums 的长度。每次都是选或不选，递归次数为一个满二叉树的节点个数，那么一共会递归 O(2ⁿ) 次（等比数列和），再算上加入答案时复制 path 需要 O(n) 的时间，所以时间复杂度为 O(n2ⁿ)。
空间复杂度：O(n)。返回值的空间不计。

---

方法2:

创建返回二维数组 ans ，和临时存储信息的数组 path 。

进入到函数 dfs 中。如果 i==n ，则说明传进来的 nums 数组里的元素都已经递归完毕，则可以 return 。这行代码可以省略，因为当 i==n 时，不会进入循环。

进入到 for 循环中，选元素要从比已经选中的元素大的那些元素中挑选。加入到 path 中，然后进入下一层循环，把 path 加入 ans 中。

代码：

class Solution {
public:vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> ans;// 创建返回数组ansvector<int> path;int n = nums.size();auto dfs = [&](auto&& dfs,int i)->void{ans.emplace_back(path);// if(i == n)  return ;for(int j = i;j < n;j++){// 选从i到n的元素path.emplace_back(nums[j]);// 把当前数字加入到path后dfs(dfs,j + 1);path.pop_back();// 尾端删除元素，恢复现场}};dfs(dfs,0);// 入口return ans;}
};

时间复杂度：O(n2ⁿ)。

其中 n 为 nums 的长度。答案的长度为子集的个数，即 2ⁿ，同时每次递归都把一个数组放入答案，因此会递归 2ⁿ次，再算上加入答案时复制 path 需要 O(n) 的时间，所以时间复杂度为 O(n2ⁿ)。
空间复杂度：O(n)。返回值的空间不计。