乍一看，还以为又是排列组合题，但细一看，发现并未要求排列，要求保持 non-descending 的顺序。而且 subset 参差不齐，却又涵盖各种情况。

以 S = [1,2,3] 为例，其 subsets 有 8 个，全无，全有，两个，一个。这样的排列不正好是二进制的节奏吗？ 8 == 2^3 即从 000 到 111。列个表：

result	bit manipulation	bit value
[3]	[0,0,1]	1
[1]	[1,0,0]	4
[2]	[0,1,0]	2
[1,2,3]	[1,1,1]	7
[1,3]	[1,0,1]	5
[2,3]	[0,1,1]	3
[1,2]	[1,1,0]	6
[]	[0,0,0]	0

是否一目了然呢？

首先，我们拿到该 set，应进行排序，保证 non-descending，然后计算返回数组的长度：

size = std::pow(2, set.size());

接下来的难点在于，如何按照位分布，来组合 vector 的元素。譬如现在我们知道 size = 8 ：

vector<vector<int>> retv(size); // 先构造返回的二维数组
for (int i=0; i<size; ++i) // 遍历每一个 bit value, 同时也是遍历 retv
    for (decltype(set.size()) j=0; j<set.size(); ++j) // 遍历 set 中的每一个 element.
        // 如果该位 == 1
        retv[i].push_back(set[j]);

好了，问题来了，注释的那句话该怎么写？如何判断该位的值？

举例：假如现在 bit value 为 2，那么其二进制位为： [0,1,0]

第一次迭代我们希望得到 0, 第二次希望得到 1，第三次希望得到 0. 这个过程不正好是二进制数右移的过程吗？

010 >> == 001 >> == 000
  ^         ^         ^

每一次右移动的最低位值即为我们想要的，如何取得？简单，与操作即可：

(i >> j) & 0x1

这样我们就能够得知该位是 true 还是 false 了。

最后一个问题在于，由于是 push_back，所以顺序与我们所列的表格有出入，如 bit value == 1 的时候，result 成了 [1]，所以如果要严格遵循表格顺序，应该是：

retv[i].push_back(set[set.size() - j - 1]);

但显然这样很不简洁，而且保持表格的顺序并无必要，所以按上面的写法就 OK 了。