题目

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

题解

最开始看到这道题，感觉很简单，这不就回溯嘛，于是就开始着手实现了，但真开始实现后就开始踩坑了。按我之前的思考惯性，喜欢通过删除的方式去回溯，回溯图如下：

对应的实现为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


vector<vector<int>> recurse(vector<int> &nums) {
   vector<vector<int>> vv;

   for (int i = 0; i < nums.size(); i++) {
       vector<int> copy(nums);
       copy.erase(copy.begin() + i);
       vv.emplace_back(copy);
       auto ret = recurse(copy);
       vv.insert(vv.begin(), ret.begin(), ret.end());
   }

   return vv;
}

vector<vector<int>> subsets(vector<int>& nums) {
   vector<vector<int>> vv;
   vv = recurse(nums);
   return vv;
}

以题目给的123为例，我们首先拿到123，之后开始遍历删除其中的字符，进而我们得到了23、13、12这3个数字，之后对他们递归，继续进行该操作，这样我们得到了2、3、1、3、1、2、这6个字符，至此，再加上空集，我们就得到了全部的子集，但这里有个问题，重复的元素有很多，比如在单个字符中，1、2、3各重复了一次，我们需要判重，但问题是该怎么判重？如果用hash表，而C++的set和map均不支持对vector进行hash计算，所以这种实现是不行的。需要换种思路。

在我上面的思路中，是自顶向下的思考，我尝试按照自底向上的思路进行思考。但想了一下，按照我脑中的思考方式，虽然可以很容易做出来，但似乎用程序实现会很麻烦，我不知道该怎么写。。。。。

具体来说，首先我们得到1、2、3，这是长度为1的子集，之后我们我们从中取两个组合形成长度为2的子集，这样得到12、13、23。之后再在长度为2的子集基础上得到长度为3的子集，抛开重复的之后，我们就得到了123。这个组合的过程并不知道该如何实现。

后来无奈看了讨论，发现还是自己的水平不够。在讨论中共给出了3种解法。

递归

虽然自己有考虑自底向上的思考，但思路却错了，这道题实际上是有规律的，而这个规律自己并未想到。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


// 1的子集
[]、[1]
// 新增2的子集为
[2]、[1,2]
// 这样1、2的子集为
[]、[1]、[2]、[1,2]
// 新增3的子集为
[3]、[1,3]、[2,3]、[1,2,3]
// 1、2、3的子集为
[]、[1]、[2]、[1,2]、[3]、[1,3]、[2,3]、[1,2,3]

可以看到，新增一个数的子集为之前数据的所有子集之后追加新增的数字。这样我们就可以实现代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


vector<vector<int>> subsets(vector<int>& nums) {
    // base case，返回一个空集
    if (nums.empty()) return {{}};
    // 把最后一个元素拿出来
    int n = nums.back();
    nums.pop_back();
    // 先递归算出前面元素的所有子集
    vector<vector<int>> res = subsets(nums);

    int size = res.size();
    for (int i = 0; i < size; i++) {
        // 然后在之前的结果之上追加
        res.push_back(res[i]);
        res.back().push_back(n);
    }
    return res;
}

回溯

看了别人的回溯实现，我自己是真要哭了。我自己一直在想该如何自底向上实现，但一直没有思路，看了别人的回溯，果然还是自己太蠢。别人的回溯树如下：

对应的回溯实现为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


void recurse(vector<int> &nums, int pos, vector<int> track, vector<vector<int>> &vv) {
    vv.push_back(track);
    for (int i = pos; i < nums.size(); i++) {
        track.push_back(nums[i]);
        recurse(nums, i + 1, track, vv);
        track.pop_back();
    }
}

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> vv;
    vector<int> v;
    recurse(nums, 0, v, vv);
    return vv;
}

思路直接代码体现了，这种思路之前自己也有想过，但是并未跟回溯关联起来，自己一直想的是如何通过多个指针来实现这个过程，但一直感觉使用指针太复杂，因此放弃了。完全想不到这种自底向上的思路竟可用回溯实现。

二进制

以123为例，我们有3位的二进制表示123这3位是否有选择，举例如下：

二进制	值
000	[]
001	[3]
010	[2]
011	[2,3]
100	[1]
101	[1,3]
110	[1,2]
111	[1,2,3]

我们生成3 bit所有的二进制值，并映射到对应的数组即可。而3bit所有的二进制值生成也很简单，从0依次加到2^3-1即可。

对应的实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        output = []
        
        for i in range(2**n, 2**(n + 1)):
            # generate bitmask, from 0..00 to 1..11
            bitmask = bin(i)[3:]
            
            # append subset corresponding to that bitmask
            output.append([nums[j] for j in range(n) if bitmask[j] == '1'])
        
        return output

以上几种的思路的参考自：