12 ms code with explaination


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

    basically used dynamic idea, subset of ith is subset of (i-1)th append each element of subset of (i-1)th with S[i] in its tail.

    for example {1,2,3,4}

    subset of {1,2,3} is {1,2,3,12,13,23,123}

    subset of {1,2,3,4} is {1,2,3,12,13,23,123} + {1 4,2 4,3 4,12 4,13 4,23 4,123 4} + {4}


  • 0
    L

    the same idea can be used in the problem letter combination of a phone number


  • 0
    I

    subset of {1,2,3,4} is {1,2,3,12,13,23,123} + {1 4,2 4,3 4,12 4,13 4,23 4,123 4} + {4}


  • 0
    D

    yeah, you are wright. I have changed it, thanks a lot.


Log in to reply
 

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