# Share my recursive and iterative solutions

• ``````// iterative method to get each element
vector<vector<int> > subsets(vector<int> &S) {
vector<vector<int> > ans(1, vector<int>());
sort(S.begin(), S.end());

vector<int> tmp;
for (int i = 0; i < S.size(); ++i) {
int len = ans.size();
for (int j = 0; j < len; ++j) {
tmp = ans[j];
tmp.push_back(S[i]);
ans.push_back(tmp);
}
}

return ans;
}

// recursive backtracing
vector<vector<int> > subsets(vector<int> &S) {
vector<vector<int> > ans;
if (S.size() <= 0) return ans;

sort(S.begin(), S.end());
if (S.size() == 1) {
ans.push_back(vector<int>());
ans.push_back(S);
return ans;
}

vector<int> tmp;
vector<int> a(S.begin()+1, S.end());
ans = subsets(a);
int n = ans.size();
for (int i = 0; i < n; ++i) {
tmp = ans[i];
tmp.insert(tmp.begin(), *S.begin());
ans.push_back(tmp);
}

return ans;
}``````

• Many thanks.
Your recursive version is still taking use of the iteration idea following the first version.
The complete recursive version will need to call subsets twice inside subsets which is really hard to track by human mind.
Nice post anyway.

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