Subsets II

 

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],
  []
]

禁止重复，就使用set，map等容器，就可以很简单解决了。

class Solution {
public:
	vector<vector<int> > subsetsWithDup(vector<int> &S) 
	{
		sort(S.begin(), S.end());
		vector<vector<int> > rs(1);
		vector<int> temp;
		set<vector<int> > us;
		us.insert(temp);

		for (int i = 0; i < S.size(); i++)
		{
			for (int j = rs.size()-1; j>=0; j--)
			{
				temp = rs[j];
				temp.push_back(S[i]);
				rs.push_back(temp);
				us.insert(temp);
			}
		}
		rs.clear();
		rs.assign(us.begin(), us.end());
		return rs;
	}

	vector<vector<int> > subsetsWithDup2(vector<int> &S) 
	{
		sort(S.begin(), S.end());
		vector<vector<int> > rs(1);
		vector<int> temp;
		set<vector<int> > us;
		us.insert(temp);

		for (int i = 0; i < S.size(); i++)
		{
			for (int j = rs.size()-1; j>=0; j--)
			{
				temp = rs[j];
				temp.push_back(S[i]);
				rs.push_back(temp);
				us.insert(temp);
			}
			rs.assign(us.begin(),us.end());
		}
		return rs;
	}
};

//2014-2-14 update
	vector<vector<int> > subsetsWithDup(vector<int> &S) 
	{
		sort(S.begin(), S.end());
		vector<vector<int> > rs(1);
		unordered_set<vector<int> > sv(rs.begin(), rs.end());
		for (int i = 0; i < S.size(); i++)
		{
			for (int j = rs.size() - 1; j >= 0 ; j--)
			{
				rs.push_back(rs[j]);
				rs.back().push_back(S[i]);
				sv.insert(rs.back());
			}
			rs.assign(sv.begin(), sv.end());
		}
		return rs;
	}