题解 | #集合的所有子集#

class Solution {
public:
    void subset(vector<int> &S, vector<vector<int>> &vec, vector<int> sub, int start, int k) {
        // 和排列数组相似，不同点：多了一个变量k来表示应该压入数组中的每个集合总数
        if(k == sub.size()) {
            vec.push_back(sub);
            return;
        }
        for(int i = start; i < S.size(); i++) {
            sub.push_back(S[i]);
            subset(S, vec, sub, i + 1, k);
            sub.pop_back();
        }
    }
    vector<vector<int> > subsets(vector<int> &S) {
        vector<vector<int>> res;
        int size = S.size();
        sort(S.begin(), S.end());
        if(size == 0)
            return res;
        vector<int> sub;
        // 先将空集合的情况压入res数组
        res.push_back(sub);
        // 将数组长度从1到size的情况一次遍历
        for(int i = 1; i <= size; i++) {
            subset(S, res, sub, 0, i);
        }
        return res;
    }
};