这道题有两个思路：一个就是基于 [63. Subsets](../63. Subsets) 的方案，只需要用一个 set 存储最后结果即可，（或者手动去重(unique)）。

这次我采用了另一种思路，即，从根本上避免重复项的插入。

按照题意，假如存在重复项：[1,2,2], 我们构造一个 vector<vector<int>> ret, 并初始化即赋予肯定有的一个 subset: []

vector<vector<int>> ret{{}};
// 遍历 S
for (size_t i=0; i<S.size(); ++i)
    // 假如没有重复项这回事，我们希望遵循以下规律组建 subset
    // i == 0 (S[i] == 1) : [] -> [],[1]    (size == 1)
    //                      ^         ^
    //                      1         *
    // i == 1 (S[i] == 2) : [],[1] -> [],[1],[2],[1,2]  (size == 2)
    //                      ^   ^             ^    ^
    //                      2   2             *    *
    // i == 2 (S[i] == 2) : [],[1],[2],[1,2] -> [],[1],[2],[1,2],[2],[1,2],[2,2],[1,2,2]    (size == 4)
    //                      ^   ^   ^    ^                       ^     ^     ^      ^
    //                      2   2   2    2                       *     *     *      *
    //                                                          !!!   !!!
    // 按照上述步骤，很明显发现了存在重复项的插入(!!!)，如何避免呢？
    // 从重复项的产生入手观察，[2]和[1,2] 两个重复项是对 []和[1] 插入 2 产生的。而在此之后的插入，并不会产生重复项。
    // 这个 2 又是怎么来的呢？这个例子不好，有太多的 2，容易迷惑，其实用别的例子试试可以看出，2 代表的是上一次迭代的 size
    // 而这个 size 是什么？这就很明显了，就是我们生成 subset 需要的迭代次数。
    // 假设 S[i] 是一个重复值，可以看出，ret中[上一次size]项之前的元素插入 S[i] 会产生重复项，而[上一次size]项之后的则不会。
    // 所以[插入]工作，应该有一个范围，设起始为 b, 结束为 e，有：
    size_t b = i && S[i] == S[i-1] ? e  : 0;
    //         ^         ^           ^    ^
    //        i>=1   出现重复项 上次的结束 重新开始
    size_t e = ret.size();
    for (; b < e; ++b)
        ret.insert(ret.end(), ret[b])->push_back(S[i]);
        //                      ^                 ^
        //               先将上一次迭代结果插入    然后修改该结果，即逐一插入 S[i]，如上图规律

这个思路是非常朴素的，上一道题其实也可以用这个思路来解，只不过上一道题里，二进制位的规律实在太明显，便会放弃这种类似穷举的方法。

但这道题里，我们在穷举的同时，也在排除重复项的干扰，却显得十分高效。

从 AC 后的效率图可以看出，这也是一个主流解法。