给定一个包含不重复整数的数组 nums，返回它的所有子集。例如 [1,2,3] 的所有子集为：

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

递归（回溯法）

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> sub;    // 初始为空, 空集也是一种情况
        genSubsets(nums, 0, sub, res);
        return res; 
    }
    void genSubsets(vector<int>& nums, int start, vector<int>& sub, vector<vector<int>>& res) {
        res.push_back(sub);    // 将新的情况加入结果集
        for (int i = start; i < nums.size(); i++) {
            sub.push_back(nums[i]);
            genSubsets(nums, i + 1, sub, res);    // 下一次迭代起始位置是 i+1
            sub.pop_back();
        }
    }
};

迭代法

初始化结果集合：[[]]
把第一个数字附在现有的所有子集之后，将新子集加入结果集：[[], [1]];
把第二个数字附在现有的所有子集之后，将新子集加入结果集：[[], [1], [2], [1, 2]];
...
直到遍历次数等于数组大小。

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res(1, vector<int>());    // 初始化包含一个空集
        for (int i = 0; i < nums.size(); i++) {
            int n = res.size();
            for (int j = 0; j < n; j++) {
                res.push_back(res[j]);    // 复制一遍当前结果
                res.back().push_back(nums[i]);    // 在这个结果的末尾添加上一个元素
            }
        }
        return res;
    }
};

比特操作

求集合的所有子集，即求集合元素的所有组合方式，每个元素都只有两种可能性：在子集中和不在子集中。由此联想到可以用 bit 值来表达。
也可以换另一种思路来理解这个算法，对于例子 [1, 2, 3]，1 在每两个连续的子集中就会出现一次， 2 在每四个连续的子集中出现两次，3 在每八个连续的子集中出现三次，如下：
[], [], [], [], [], [], [], []
[], [1], [], [1], [], [1], [], [1]
[], [1], [2], [1, 2], [], [1], [2], [1, 2]
[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int num_subset = pow(2, nums.size());    // 最后结果的个数是 2 的 nums.size() 次幂
        vector<vector<int> > res(num_subset, vector<int>());    // 初始都为空
        for (int i = 0; i < nums.size(); i++)    // 对每个数字
            for (int j = 0; j < num_subset; j++)
                if ((j >> i) & 1)    // // j 的第 i 位是 1 时, 表明数字应该被加入这个结果
                    res[j].push_back(nums[i]);
        return res;  
    }
};