前言
今天刷 Leetcode 题目遇到一个求一个无重复元素数组的全部子集，遇到这种题目如果是以前我可能会使用迭代法，首先将一个空数组加入结果集，然后遍历数组中的元素，对于每个元素，遍历结果集中的全部子集，向全部子集中加入当前元素得到新的子集，再将这些新的子集加入结果集。但现在我第一想到的不是这个解法，而是回溯法，因为回溯的意义就是找到所有可能的结果。并且回溯法写起来给人的感觉特别优雅，又易读易懂，掌握了之后感觉真的很好。
我写好了之后一遍提交通过，和往常一样我又来到了讨论区，看到了官方题解的一个解法是利用二进制数。我震惊了，这都能扯上关系？看到官方题解有这个方法，那么国际版高赞一定也有这个解法，并且代码更简洁，讲解更易懂。于是我果然在高赞区看到了。这就是方法三。
我们先看题目描述：
解法一：普通迭代法
思路
- 首先将空集加入结果集中，用作母体产生后面的结果。
- 遍历数组，对于当前的元素
- 遍历之前结果集中的子集，将子集加入到结果集中，再将当前元素加入到尾部。
代码
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> res;
res.push_back({});
for (int num : nums) {
int n = res.size();
for (int i = 0; i < n; ++i) {
res.push_back(res[i]);
res.back().push_back(num);
}
}
return res;
}
};
复杂度
- 时间复杂度：$O(N*2^N)$ 。
- 空间复杂度：$O(N*2^N)$ 。
方法二：回溯法
思路
定义回溯函数，从start开始遍历nums数组中的元素，对于当前元素有两种选择：
- 选择加入结果集：那么就从下一个元素开始调用回溯函数
- 不加入结果集：什么也不用做。
代码
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
backtrack(nums, 0);
return res;
}
private:
vector<vector<int>> res;
vector<int> tmp;
void backtrack(vector<int> &nums, int start) {
res.push_back(tmp);
for (int i = start; i < nums.size(); ++i) {
tmp.push_back(nums[i]);
backtrack(nums, i+1);
tmp.pop_back();
}
}
};
复杂度
- 时间复杂度：$O(N*2^N)$ 。
- 空间复杂度：$O(N*2^N)$ 。
方法三：二进制法
思路
一个包含 n 个元素的集合的子集数量为 $2^n$ 。因为每个元素可以选择选或者不选。深度利用这个规则，我们用二进制数来表示每个元素的选或者不选。那么我们需要一段长为n+1的二进制数。因为我们需要的二进制数范围为：000…(n个0，表示全部不选，也就是空集) 到 111…(n个1，表示全选，也就是数组本身)。因此我们的limit 就是总的子集数量。
从0遍历到limit-1，看看当前的二进制数，当前的二进制数中的哪一位为1，就将nums数组中的哪一位加入结果集中。就是这么简单！！！
代码
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
int n = nums.size(), limit = 1 << n;
vector<vector<int>> res(limit);
for (int i = 0; i < limit; ++i) {
for (int j = 0; j < n; ++j) {
if ((i >> j) & 1) {
res[i].push_back(nums[j]);
}
}
}
return res;
}
};
复杂度
- 时间复杂度：$O(N*2^N)$ 。
- 空间复杂度：$O(N*2^N)$ 。