如何求一个集合所有的子集

记求一个集合的所有子集的三种方法

来源：记求一个集合的所有子集的三种方法-zhyjc6's Blog

前言

今天刷 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∗2N)O(N∗2N) 。
• 空间复杂度：O(N∗2N)O(N∗2N) 。

方法二：回溯法

思路

定义回溯函数，从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∗2N)O(N∗2N) 。
• 空间复杂度：O(N∗2N)O(N∗2N) 。

方法三：二进制法

思路

一个包含 n 个元素的集合的子集数量为 2n2n 。因为每个元素可以选择选或者不选。深度利用这个规则，我们用二进制数来表示每个元素的选或者不选。那么我们需要一段长为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∗2N)O(N∗2N) 。
• 空间复杂度：O(N∗2N)O(N∗2N) 。