首页 > 代码库 > leetcode-Subsets-78

leetcode-Subsets-78

输入一个数组,求所有子集

也是选择问题,在上一题的基础上枚举子集长度,然后dfs+回溯选择。同样注意去重

 1 class Solution { 2 public: 3     void dfs(vector<int> a,int i,vector<vector<int> > &v,vector<int> vv,int k){ 4         if(vv.size()==k){ 5             v.push_back(vv); 6             return; 7         } 8         for(int j=i+1;j<a.size();j++){ 9             if(j!=i+1&&a[j]==a[j-1]) continue;10             vv.push_back(a[j]);11             dfs(a,j,v,vv,k);12             vv.pop_back();13         }14     }15     vector<vector<int> > subsets(vector<int>& nums) {16         int len=nums.size();17         vector<vector<int> > v;18         if(len==0) return v;19         vector<int> vv;20         v.push_back(vv);21         sort(nums.begin(),nums.end());22         for(int k=1;k<=len;k++){23             for(int i=0;i<len;i++){24                 vv.push_back(nums[i]);25                 dfs(nums,i,v,vv,k);26                 vv.pop_back();27             }28         }29         return v;30     }31 };

 

leetcode-Subsets-78