SubsetsII.txt

problem：
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,
If S = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

-------------------------------------------------------------

solution：
//对原数组中存在重复元素时的解决方案
void subsetsWithDup_aux(vector<int> &S, int curPos, vector<int> &tmp, vector<vector<int> > &ret)
{
  ret.push_back(tmp);
    for(int i = curPos; i < S.size(); ++i)
    {
        if(i != curPos && S[i] == S[i - 1])continue;
        tmp.push_back(S[i]);
        subsetsWithDup_aux(S, i + 1, tmp, ret);
        tmp.pop_back();
    }
}
 
vector<vector<int> > subsetsWithDup(vector<int> &S)
{
    sort(S.begin(), S.end());
    vector<int> tmp;
    vector<vector<int> > ret;
    subsetsWithDup_aux(S, 0, tmp, ret);
    return ret;
}