dfs

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;

    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return res;    
    }

    void dfs(vector<int>& nums, int u) {
        if (u == nums.size()) {
            res.push_back(path);
            return;
        }

        dfs(nums, u + 1);//不选当前数，递归下一层
        path.push_back(nums[u]);//选当前数
        dfs(nums, u + 1);//递归下一层
        path.pop_back();//回溯,恢复现场
    }
};

二进制

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        int n = nums.size();
        for (int i= 0; i < 1 << n; i++) {//一直枚举到2^n - 1位
            vector<int> path;
            for (int j = 0; j < n; j++) {//枚举一下每位是0还是1,代表选还是不选
                if (i >> j & 1) {//这里要看i的第j位,所以将第j位移到个位再&1，就知道是0还是1了
                    path.push_back(nums[j]);//如果是1说明要选，将其加到方案中
                }
            }
            res.push_back(path);//将当前方案记录到答案中
        }
        return res;
    }
};