12 ms code with explaination


  • 3
    D
    class Solution {
    public:
    	vector<vector<int> > subsetsWithDup(vector<int> &S) {
    		sort(S.begin(),S.end());
    		vector<vector<int>> results;
    		vector<vector<int>> append;
    		//from less to more
    		for (unsigned i = 0; i < S.size(); ++i){
    			if (i>0 && S[i] != S[i - 1]){
    				append = results;
    			}
    			for (vector<vector<int>>::iterator iter = append.begin(); iter != append.end(); ++iter){
    				iter->push_back(S[i]);
    				results.push_back(*iter);
    			}
    			if (i ==0 || i > 0 && S[i] != S[i - 1]){
    				vector<int> temp;
    				temp.push_back(S[i]);
    				append.push_back(temp);
    				results.push_back(temp);
    			}
    		}
    		vector<int> emp;
    		results.push_back(emp);
    		return results;
    	}
    };
    

    same idea as I used in subset I
    but in this problem, we need to handle the duplicate problem
    by observing some test case, we can find when S[i] == S[i-1] ,subset of i th only added those vector<int> which contains S[i] compared to subset of (i-1)th . Those vector<int> are appended when iteration get i-1 from i-2 , so we need to store the appended elements in case we use it.
    for example,{1,2,3,3}
    subset of {1,2} : {1,2,12}
    subset of {1,2,3} : {1,2,12} + {1 3,2 3,12 3} = {1,2,12,13,23,123}
    subset of {1,2,3,3} : {1,2,12,13,23,123} + {1 33,2 33,12 33}


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.