leetcode 热题100（78. 子集）dfs回溯 c++
链接：78. 子集 - 力扣（LeetCode）
给你一个整数数组 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] <= 10nums中的所有元素 互不相同
思路
这题根全排列那题很像，但是这里是只添加子集，就是不一定元素为数组装了n个才要添加，只要是满足顺序是从左往右的子集即可，那么我们此时定义一个 cur 变量来表示我们当前遍历到哪个数组，每个考虑两种情况 1.添加这个元素 2.不添加这个元素，那么我们肯定可以考虑所有的情况了
代码
class Solution {
public:
int n;
vector<vector<int>> res;
bool st[10];
vector<vector<int>> subsets(vector<int>& nums) {
n = nums.size();
vector<int> tmp;
dfs(0,tmp,nums);
return res;
}
void dfs(int cur,vector<int> tmp,vector<int>& nums){
if(cur==n){
res.push_back(tmp);
return;
}
tmp.push_back(nums[cur]);
dfs(cur+1,tmp,nums);
tmp.pop_back();
dfs(cur+1,tmp,nums);
}
};