#include <iostream>
#include <vector>
#include <map>

using namespace std;

vector<vector<int> > SubsetsWithDup(vector<int> &S) 
{
	map<int, int> counter;
	for (int i = 0; i < S.size(); ++i)
		counter[S[i]]++;
    
    map<int, int>::iterator beg = counter.begin();
    map<int, int>::iterator end = counter.end();
    vector<vector<int> > results;
    results.push_back(vector<int>());

    //append new number to each of previous subset to generator new subsets
    while(beg != end)
    {
    	int count = (*beg).second;
    	int num = (*beg).first;
    	int size = results.size();
    	int base = 0;
    	while(count-- > 0)
    	{
    		for (int i = 0; i < size; ++i)
    		{
    			results.push_back(results[base + i]);
    			results.back().push_back(num);
    		}
    		base+=size;
    	}
		
		++ beg;
    }

    return results;
}

void PrintVV(vector<vector<int> >  v)
{
	for (int i = 0; i < v.size(); ++i)
	{
		cout << (i+1) << ":\t";
		for (int j = 0; j < v[i].size(); ++j)
			cout << v[i][j] << ",\t";
		cout << endl;
	}
}

int main(int argc, char** argv)
{
	int A[] = {1,2,2};
	vector<int> Av;
	for (int i = 0; i < sizeof(A)/sizeof(int); ++i)
		Av.push_back(A[i]);

	PrintVV(SubsetsWithDup(Av));
	return 0;
}