Subsets II
Given a collection of integers that might contain duplicates, S, return all possible subsets.
Note:
For example,
If S = [1,2,2], a solution is:
[ [2], [1], [1,2,2], [2,2], [1,2], [] ]
举例说明我的算法：
设S={1,2,2}，则size=3
在不考虑重复的情况下，子集共有2^3=8个
分别为：
【1,2,2】
0,0,0 {}
0,0,1 {2}
0,1,0 {2}
0,1,1 {2,2}
1,0,0 {1}
1,0,1 {1,2}
1,1,0 {1,2}
1,1,1 {1,2,2}
1表示对应位的元素存在于集合中，0表示不存在。
因此只要从0遍历到2^size - 1，如果对应位为1，则将S中相应元素加入当前集合。
对于Note的两点要求：
1、sort函数对集合排序
2、使用map去重，存在即去除。
class Solution { public: vector<vector<int> > subsetsWithDup(vector<int> &S) { vector<vector<int> > result; map<vector<int>, bool> m; int size = S.size(); for(int i = 0; i < pow(2.0, size); i ++) { int tag = i; vector<int> cur; for(int j = size-1; j >= 0; j --) { if(!tag) break; if(tag%2 == 1) { cur.push_back(S[j]); } tag >>= 1; } sort(cur.begin(), cur.end()); if(m.find(cur) == m.end()) { m[cur] = true; result.push_back(cur); } } return result; } };
原文：http://www.cnblogs.com/ganganloveu/p/4143592.html