Description

Given a set of distinct integers, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example,

If nums = [1,2,3], a solution is:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

给一个整数集合，要求求出它的所有子集。

Solution

对这个问题第一反应是传统的循环写法和搜索写法都不太好写，控制条件比较复杂。

但这里有个关键的隐含条件是每个子集之间是“连续”的，而且需要所有的子集。

事实上，借鉴信息编码原理，问题就非常简单了。

借鉴计算机整数编码原理，每一个整数由一个二进制数所表示，那么这里每一个子集由一个二进制数表示，例如题目所给例子：

000 代表 []
001 代表 [3]
010 代表 [2]
011 代表 [2,3]
100 代表 [1]
101 代表 [1,3]
110 代表 [1,2]
111 代表 [1,2,3]
​
这样一来问题就变成了在[0,2nums.size())范围内的线性枚举，中间只需要用“与”运算寻找每个二进制中有的1即可。
担心用int会发生溢出？溢出需要枚举232次，这么大的枚举量必定TLE的，也即TLE必定发生在溢出之前，所以题目测试数据 nums 数组的长度应该远远不到32 。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<vector<int> > subsets(vector<int>& nums)
{
    vector<vector<int> > ret;
    int total = 1 << nums.size();
    for(int i = 0; i < total; i++)
    {
        vector<int> v;
        for(int offset = 0; offset < 32; offset++)
        {
            if(i & 1 << offset) v.push_back(nums[offset]);
        }
        ret.push_back(v);
    }
    return ret;
}