加班回来同事微信发来一道题目说这是整个leetcode中最棒的一道题目获益良多，本着我坚决不信的态度，尝试了两种平平无奇的解法后正打算开喷，在讨论区看到一种位运算的方法，好吧，我承认这是最棒的一道题。

Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

迭代法 常规解法

这里的过程执行过程是：
以题目中的输入为例子
第一步添加一个空的vector [[]]
添加 1之后[]: [[], [1]];（这里实际上是又插入一个空的vector，然后在空的vector中添加1）
添加 2 之后[] and [1]: [[], [1], [2], [1, 2]];
添加 3 之后[], [1], [2] and [1, 2]: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]].

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> subs = {{}};
        for (int num : nums) {
            int n = subs.size();
            for (int i = 0; i < n; i++) {
                subs.push_back(subs[i]); 
                subs.back().push_back(num);
            }
        }
        return subs;
    }
}; 

迭代法应该是解决这类问题中最好理解的方法，执行速度同样非常优秀。

Runtime: 4 ms, faster than 97.25% of C++ online submissions for Subsets.
Memory Usage: 6.6 MB, less than 100.00% of C++ online submissions for Subsets.

递归方法 常规解法

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> subs;
        vector<int> sub;
        subsets(nums, 0, sub, subs);
        return subs;
    }
private:
    void subsets(const vector<int>& nums, int i, vector<int>& sub, vector<vector<int>>& subs) {
        subs.push_back(sub);
        for (int j = i; j < nums.size(); j++) {
            sub.push_back(nums[j]);
            subsets(nums, j + 1, sub, subs);
            sub.pop_back();
        }
    }
};

位运算 可遇而不可求

假设vector中有n个元素，每个元素要么出现要么不出现，所以，子集有2的n次方个，等等这不就和二进制位对上了吗，假设3个元素，000-111就是8个元素，不就对应全排列吗。
以{1,2,3}为例
000 对应 { }
001 对应 {3}
010 对应 {2}
011 对应 {2,3}
100 对应 {1}
101 对应 {1,3}
110 对应 {1,2}
111 对应 {1,2,3}
解法是真的巧妙，一般谁能想到这种解法???

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &nums) {
        int elem_num = nums.size();
        //元素总个数
        int subset_num = pow (2, elem_num);
        vector<vector<int> > subset_set (subset_num, vector<int>());
        for (int i = 0; i < elem_num; i++)
            for (int j = 0; j < subset_num; j++)
                if ((j >> i) & 1)
                    subset_set[j].push_back (nums[i]);
        return subset_set;
    }
};