// Problem i
class Solution {
public:
 	vector<vector<int> > subsets(vector<int> &S) {
		vector<vector<int>> result;
		if (!S.size())
			return result;
		result.push_back(vector<int>());
		sort(S.begin(), S.end());
		for (int i = 0; i < S.size(); ++ i){
			int num = result.size();
			for (int j = 0; j < num; ++ j){				
				result.push_back(result[j]);
				result[j].push_back(S[i]);
 			}
 		}
		return result;
 	}
};

//Problem ii
class Solution {
public:
 	vector<vector<int> > subsetsWithDup(vector<int> &S) {
		vector<vector<int> > result;
		result.push_back(vector<int>());
		sort(S.begin(), S.end());
		for (int i = 0; i < S.size(); ++ i){
			int nSame = 1;
			while(i < S.size() - 1 && S[i] == S[i+1])
				nSame ++, i ++;
			int num = result.size();
			for (int k = 0; k < nSame; ++ k){				
				for (int j = 0; j < num; ++ j){				
					result.push_back(result[j]);
					result[j].push_back(S[i]);
	 			}
 			}
 		}
		return result;
 	}
};

class Solution {
public:
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
    	vector<vector<int> > result;
    	sort(S.begin(),S.end());
  		
  		vector<int> current;
  		nextElement(S, 0, result, current);

  		return result;
    }
    void nextElement(vector<int>& S, int start, vector<vector<int> > &result, vector<int>& current){
    	result.push_back(current);
    	for (int i = start; i < S.size(); ++ i){
    	    if (i - start && S[i] == S[i-1])
    	        continue;
    		current.push_back(S[i]);
    		nextElement(S, i+1, result, current);
    		current.pop_back();
    	}

    }
};