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:
1[
2 [2],
3 [1],
4 [1,2,2],
5 [2,2],
6 [1,2],
7 []
8]
思路：
复习（？）一下 枚举子集的三种写法
（还有种更飘逸的…先不写了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]);
19
20 sort(tmp.begin(),tmp.end());
21 int siz = tmp.size();
22// for ( int i = 0 ; i < siz ; i++) printf("%d ",tmp[i]);printf("\n");
23 se.insert(tmp);
24 return;
25 }
26 B[cur] = 1;
27 get_subset(n,B,cur+1,nums);
28 B[cur] = 0;
29 get_subset(n,B,cur+1,nums);
30 }
31 vector<vector<int>> subsetsWithDup(vector<int>& nums) {
32 int siz = nums.size();
33 if (siz==0) return res;
34 get_subset(siz,B,0,nums);
35 for ( auto &it : se)
36 {
37 res.push_back(it);
38 }
39 return res;
40 }
41};