leetcode 90. Subsets II (枚举子集)
Given a collection of integers that might contain duplicates, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,2], a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
思路：
复习（？）一下 枚举子集的三种写法
（还有种更飘逸的...先不写了orz
这道题我用位向量法A的。。
1/* ***********************************************
2Author :111qqz
3Created Time :2017年04月05日 星期三 17时15分34秒
4File Name :90.cpp
5************************************************ */
6class Solution {
7public:
8 set<vector<int> >se;
9 int B[1005];
10 vector <vector<int> >res;
11 void get_subset(int n,int *B,int cur,vector<int>& nums)
12 {
13// cout<<"cur:"<<cur<<endl;
14 if (cur==n) //from 0
15 {
16 vector<int>tmp;
17 for ( int i = 0 ; i < n ; i++)
18 if (B[i]) tmp.push_back(nums[i]);
1 sort(tmp.begin(),tmp.end());
2 int siz = tmp.size();
3// for ( int i = 0 ; i < siz ; i++) printf("%d ",tmp[i]);printf("\n");
4 se.insert(tmp);
5 return;
6 }
7 B[cur] = 1;
8 get_subset(n,B,cur+1,nums);
9 B[cur] = 0;
10 get_subset(n,B,cur+1,nums);
11 }
12 vector<vector<int>> subsetsWithDup(vector<int>& nums) {
13 int siz = nums.size();
14 if (siz==0) return res;
15 get_subset(siz,B,0,nums);
16 for ( auto &it : se)
17 {
18 res.push_back(it);
19 }
20 return res;
21 }
22};