题目描述
Given a collection of integers that might contain duplicates, S, return all possible subsets.
Note:
Elements in a subset must be in non-descending order(非下降顺序，升序).The solution set must not contain duplicate subsets.
For example,IfS =[1,2,2], a solution is:[ [2], [1], [1,2,2], [2,2], [1,2], [] ]
思路
为了保证不重复，我们规定产生的子集内部的元素按照升序。当前前缀+一个不同的元素扩展,由不同的前缀扩展的子集当然是不同的，而由相同前缀扩展来的子集，由于是+一个不同的元素进行的扩展，所以也是不同的，这就保证这种方法不会发生重复，其实，这个问题还可以利用层次遍历(宽度优先遍历)，按照子集的长度大小，一圈一圈的长度加1来解决。
代码
class Solution {
public:
vector<vector<int> > subsetsWithDup(vector<int> &S) {
vector<vector<int>> ret;
vector<int> pre;
ret.push_back(pre);
sort(S.begin(),S.end());//排序是为了去重的需要
subsetsWithDupCore(S,0,ret,pre);
return ret;
}
void subsetsWithDupCore(vector<int> &S,int start,vector<vector<int>> &ret,vector<int> &pre)
{
if(start == S.size())
return;
//枚举要扩展的一个元素的不同可能情况
for(int i = start;i < S.size();i++)
{
if(i!=start && S[i] == S[i-1])
continue;
pre.push_back(S[i]);
ret.push_back(pre);
subsetsWithDupCore(S,i+1,ret,pre);
pre.pop_back();
}
}
};