回溯大法好

同样是回溯...

回溯模板如下：

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();
            }
        }
    }
};