阅读此篇之前建议阅读 DFS求全排列总结 ，求子集相对于求全排列来说简单不少，因为我们在考虑方案时，对于每一个数，我们只有选或不选两种选择，因此如果像全排列那样画出递归搜索树，求子集的递归搜索树正好是一棵满二叉树。所有方案刚好是所有叶子结点，因此对于一个大小为n的集合来说，所有子集的个数为$2^n$个。

dfs + 回溯法

和全排列的做法一样，当我们走到叶子结点时，就把该路径加入方案中。如果还没有走到叶子节点，那么对于枚举的当前数，我们有两种选择，选或不选，做出选择再递归到下一层，同时记得回溯。

C ++代码

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

位运算法

在前面的分析中我们知道对于每个数，我们可以选或者不选，两种选择刚好对应两种状态，因此我们可以采用位运算的思路进行求解。对于一个大小为n的集合来说，我们需要用一个n位二进制数来表示每个数的选择状态，所有方案刚好是所有叶子结点，所有子集的个数为$2^n$个，所以每个叶子结点的状态刚好可以用0 ~ $2^n - 1$中的二进制数表示。

例如对于集合[1, 2, 3]

C ++代码

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        int p = 1 << n;
        vector<vector<int>> res(p);

        for (int i = 0; i < p; i ++)
            for (int j = 0; j < n; j ++)
                if ((i >> j) & 1)
                    res[i].push_back(nums[j]);

        return res;    
    }
};