1. 递归

每次递归，当前位置的数字可以选择或者不选择。

class Solution {
public:
    vector<vector<int> > res;
    void dfs(vector<int>& S, vector<int> tmp, int start){
        res.push_back(tmp);
        if(start == S.size()){
            return;
        }
        for(size_t i = start; i < S.size(); i++){
            tmp.push_back(S[i]);
            dfs(S, tmp, i + 1);
            tmp.pop_back();
        }
    }
    
    vector<vector<int> > subsets(vector<int> &S) {
        if(S.empty()) return res;
        sort(S.begin(), S.end());
        dfs(S, vector<int>(), 0);
        return res;
    }
};

2. 位运算：n个元素的子集共有2^n个.

将0~2^n-1的每一个数转换为n位的二进制数来看，如果第0~n-1的某一位为1，则选择对应位置的数。遍历完即可获得所有子集。

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        vector<vector<int> > res;
        vector<int> tmp;
        int n = S.size();
        if(S.empty()) return res;
        sort(S.begin(), S.end());
        for(int i = 0; i < pow(2, n); i++){
            for(int j = 0; j < n; j++){
                if((i >> j) & 1){
                    tmp.push_back(S[j]);
                }
            }
            res.push_back(tmp);
            tmp.clear();
        }
        return res;
    }
};