同样是回溯...
回溯模板如下:
void backtrack(...) { // 递归停止条件 for (int i = begin; i < end; i++) { // 更新状态 backtrack(...); // 回退状态 } }
详细代码如下:
class Solution { public: vector<vector<int> > subsets(vector<int> &S) { sort(S.begin(), S.end()); vector<vector<int> > ans; int len = S.size(); vector<int> p; vector<bool> visit(len, false); for (int i = 0; i <= len; i++) { backtrack(S, ans, i, p, visit, 0); } return ans; } void backtrack(vector<int> &S , vector<vector<int> > & ans, int size, vector<int> & path, vector<bool> & v, int begin) { if (path.size() == size) { vector<int> p(path); ans.push_back(p); return; } for (int i = begin; i < S.size(); i++) { if (!v[i]) { v[i] = true; path.push_back(S[i]); backtrack(S, ans, size, path, v, i+1); v[i] = false; path.pop_back(); } } } };