9.4 Write a method to return all subsets of a set.
LeetCode上的原题，请参见我之前的博客Subsets 子集合和Subsets II 子集合之二。
解法一：
class Solution {
public:
vector<vector<int> > getSubsets(vector<int> &S) {
vector<vector<int> > res();
for (int i = ; i < S.size(); ++i) {
int size = res.size();
for (int j = ; j < size; ++j) {
res.push_back(res[j]);
res.back().push_back(S[i]);
}
}
return res;
}
};解法二：
class Solution {
public:
vector<vector<int> > getSubsets(vector<int> &S) {
vector<vector<int> > res;
vector<int> out;
getSubsetsDFS(S, , out, res);
return res;
}
void getSubsetsDFS(vector<int> &S, int pos, vector<int> &out, vector<vector<int> > &res) {
res.push_back(out);
for (int i = pos; i < S.size(); ++i) {
out.push_back(S[i]);
getSubsetsDFS(S, i + , out ,res);
out.pop_back();
}
}
};解法三：
class Solution {
public:
vector<vector<int> > getSubsets(vector<int> &S) {
vector<vector<int> > res;
int max = << S.size();
for (int i = ; i < max; ++i) {
vector<int> out = convertIntToSet(S, i);
res.push_back(out);
}
return res;
}
vector<int> convertIntToSet(vector<int> &S, int k) {
vector<int> sub;
int idx = ;
for (int i = k; i > ; i >>= ) {
if ((i & ) == ) {
sub.push_back(S[idx]);
}
++idx;
}
return sub;
}
};