leetcode hot100刷题日记——35.子集

解答：

方法一：选or不选的dfs（输入视角）

思路：[1,2,3]的全部子集可以看成是对数组的每一位数字做选择。
eg.空集就是一个数字都不选，[1,2]就是1，2选，3不选。

class Solution {
public:
	vector<vector<int>> res;//存所有结果用的
	vector<int> path;//存单个结果
	void dfs(vector<int>&nums,int pos,int size){
		if(pos==size){//遍历到了数组的最后，做完了所有的选择，为什么size是n前面的日记解释过了~
			res.emplace_back(path);//把单个结果放进总结果里面，注意emplace_back函数，之前也出现过几次了
			return;
		}
		//对于单个数字，我们的选择有两种
		//1.选
		path.push_back(nums[pos]);//放进单个数组
		dfs(nums,pos+1,size);//做好选择后再去做下一个选择
		path.pop_back();//回溯的精髓，恢复原状
		
		//2.不选
		dfs(nums,pos+1,size);//直接做下一个选择	
	}
	
	vector<vector<int>> subsets(vector<int>& nums) {
		int size=nums.size();
		dfs(nums,0,size);
		return res;
	}
};

时间复杂度：O(n2^n)
空间复杂度：O(n)

方法二：选or不选的dfs（输出视角）

思路：如果选了数组的某一位添加到答案末尾，那么下一个要添加到答案末尾的数，就要在这个某一位后面的数字中枚举了。用循环来帮忙

举个例子哦，对于子集[1,2,3]来说，从1开始思考，1要不要在我的子集里面，要的话那就放进去，不要的话那就恢复现场
再接着考虑下一位2……

class Solution {
public:
	vector<vector<int>> res;//存所有结果用的
	vector<int> path;//存单个结果
	void dfs(vector<int>&nums,int pos,int size){
		res.emplace_back(path);//每次做完这个数要不要选的结果都放进去总结果里面
		//从path的当前位置开始考虑要不要选
		for(int i=pos;i<size;i++){
			path.push_back(nums[i]);//要选
			dfs(nums,i+1,size);//下一个开始选择
			path.pop_back();//恢复现场
		}
	}
	
	vector<vector<int>> subsets(vector<int>& nums) {
		int size=nums.size();
		dfs(nums,0,size);
		return res;
	}
};

时间复杂度：O(n2^n)
空间复杂度：O(n)

方法三：二进制枚举
使用位运算来高效枚举所有可能的组合
比如[1,2,3]，我们枚举xxx所有的二进制可能（000，001，010……）如果是000就是空集，001就是把3放进去，010就是放2……

二进制数对应的这一位是1就相当于选这位数，0就是不选。

class Solution {
public:
	vector<vector<int>> subsets(vector<int>& nums) {
		int n=nums.size();
		vector<vector<int>> res(1<<n);//一共1<<n种结果
		//i是结果数，j是位数
		for(int i=0;i<(1<<n);i++){
			for(int j=0;j<n;j++){
				// 判断第j位是否为1
				if(i>>j&1)
					res[i].push_back(nums[j]);//是1的话就放进去结果
			}
		} 
		return res;
	}
};

时间复杂度：O(n2^n)
空间复杂度：O(1)