Given a set of distinct integers, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example, If nums = [1,2,3], a solution is:
[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
求一个数组的子集，使用递归的做法，使用一个临时数组【用于像栈一样】记录深搜的时候当前分支有多少个数组元素。 使用deep从0开始递增表示递归深度，当deep==nums.size()的时候为递归终点，此时将temp推入到result里面。 需要注意为了避免重复需要利用sort将数组进行排序。
class Solution { public: vector<vector<int>> subsets(vector<int>& nums) { sort(nums.begin(),nums.end()); vector<int> temp; vector<vector<int> > result; subsets(nums,temp,0,result); return result; } void subsets(vector<int>& nums,vector<int> & temp,int size,vector<vector<int> >& result){ if(size==nums.size()){ result.push_back(temp); return; } //不选当前元素 subsets(nums,temp,size+1,result); temp.push_back(nums[size]); subsets(nums,temp,size+1,result); temp.pop_back(); } };II是I的升级版，这时候里面有重复元素。 于是就是一个判重问题。 主体代码完全相同
思考一下如何进行判重，如果有一个元素的长度同当前temp相等并且在比较相等的时候可以一直比较到最后一位。这时候表明这个元素是重复的，不应当推入。
class Solution { public: vector<vector<int>> subsetsWithDup(vector<int>& nums) { sort(nums.begin(),nums.end()); vector<vector<int> > result; vector<int> temp; subsets(nums,temp,0,result); return result; } void subsets(vector<int>& nums,vector<int> temp,int size,vector<vector<int> >& result){ if(size==nums.size()){ //插入元素的时候判重 int flag=0; for(int i=0;i<result.size();i++){ //首先判断长度 if(temp.size()!=result[i].size()) continue; //对于每一个判断每一个元素 int j=0; for(;j<result[i].size() && temp[j]==result[i][j];j++); if(j==result[i].size()){ flag=1;break; } } if(!flag) result.push_back(temp); return; } subsets(nums,temp,size+1,result); temp.push_back(nums[size]); subsets(nums,temp,size+1,result); temp.pop_back(); } };