Tags

Given a set of distinct integers, 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,3], a solution is:

[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

Key: recursive

class Solution {
public:
    void getSubSets(vector<int>& S, int idx, vector<vector<int> >& result)
    {
        size_t size = S.size();
        if (idx >= size)
            return;
        size_t resultSize = result.size();
        for(size_t k=0; k<resultSize; ++k)
		{
			result.push_back(result[k]);
			result.back().push_back(S[idx]);
		}
		getSubSets(S, idx+1, result);
    }
    
    vector<vector<int> > subsets(vector<int> &S) {
        // Start typing your C/C++ solution below
        // DO NOT writ e int main() function
        sort(S.begin(), S.end());
        vector<vector<int> > result;
		if (S.size() == 0)
			return result;
		result.push_back(vector<int>());
		result.push_back(vector<int>(1, S[0]));
        getSubSets(S, 1, result);
		return result;
    }
};
Advertisements