I made a function to generate all the subsets of a length of k. Then I called this function n times with the k increased from 1 to n (n is the length of the array S). Is there a better solution? It seems we could make some uses of the generated subsets. For example, when we have all the subsets of k=1, could we use them to generate the subsets of k=2? Thanks.
Is there a better solution?


This is the C++ version with similar idea of @us917.
class Solution { public: vector<vector<int> > subsets(vector<int> &S) { // 1: sort the array // 2: each time, add in one new number to all previous sets vector <vector<int> > sets; sort(S.begin(), S.end()); vector<int> set; sets.push_back(set); for (auto i:S) { int cur_size = sets.size(); // corrected after @cecilulysess's reminder for (int j = 0; j < sets.size(); j++) { set = sets[j]; set.push_back(i); sets.push_back(set); } } return sets; } };

A correct C++ version according to @us917's idea.
The key problem for C++ is, you have to have a fixed loop size for the inner for
class Solution { public: vector<vector<int> > subsets(vector<int> &S) { sort(S.begin(), S.end()); vector<vector<int>> res; vector<int> d; int curr_size = 0; res.push_back(vector<int>{}); for (int &e : S) { curr_size = res.size(); for(int i = 0; i < curr_size; ++i) { d = res[i]; d.push_back(e); res.push_back(d); } } return res; } };

we can use stl::set to sort while insert. I got AC in 20m.
class Solution { private: void ctsbst(vector<vector<int> > &ret, set<int> &row, vector<int> &S, int n) { if(n == S.size()) { vector<int> v; set<int>::iterator it; for(it = row.begin(); it != row.end(); ++it) v.push_back(*it); ret.push_back(v); return; } row.insert(S[n]); ctsbst(ret, row, S, n+1); row.erase(S[n]); ctsbst(ret, row, S, n+1); } public: vector<vector<int> > subsets(vector<int> &S) { vector<vector<int> > ret; set<int> row; ctsbst(ret, row, S, 0); return ret; } };


//dynamic programming class Solution { public: vector<vector<int> > subsets(vector<int> &S) { vector<vector<int>> re; sort(S.begin(),S.end()); re.push_back(vector<int>()); for(int i=0;i<S.size();++i) { int size=re.size(); for(int j=0;j<size;++j) { //vector<int> tmp=re[j]; //tmp.push_back(S[i]); re.push_back(re[j]); re[re.size()1].push_back(S[i]); } } return re; } };
@us917 Your method is not efficient enough in that in each iteration ss is a copy of a former element and to add it into A, another copy is needed. Copy costs a lot of time. So my method is better because only one copy is needed to add one element. But in fact, my method is not better than recursion, even worse. For the solution of 18 elements in S, recursion costs about 4.7 seconds,and my method costs about 5.6 seconds, and your method costs about 8 seconds. But I still don't know why.Anybody can figure out?


A solution similar to @hongzhi's std::set method:
class Solution { public: vector<vector<int>> subsets(vector<int> &S) { sort(S.begin(), S.end()); // dirty vector<vector<int>> powerset; vector<int> subset; collectSubsets(S, 0, subset, powerset); return powerset; } void collectSubsets(vector<int> &S, int n, vector<int> &subset, vector<vector<int>> &powerset) { if (n < S.size()) { subset.push_back(S[n]); collectSubsets(S, n+1, subset, powerset); subset.pop_back(); collectSubsets(S, n+1, subset, powerset); } else { powerset.push_back(subset); } } };