LeetCode题目（Python实现）：子集

Dear 丶 2023-07-25 09:38 10阅读 0赞

### 文章目录 ###

*  题目
 *   *  想法一：利用二进制
     *   *  算法实现
         *  执行结果
         *  复杂度分析
     *  想法二：将二进制的想法直接运用（官方递归）
     *   *  算法实现
         *  执行结果
         *  复杂度分析
     *  小结

# 题目 #

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

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

**示例**：

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

## 想法一：利用二进制 ##

想法是按照二进制来确定集合元素，一个集合的子集数量是  2 n 2^n 2n，将0到 2 n 2^n 2n的每一个数字转化为n位二进制，可以发现其对应子集的情况。比如给出的示例中，有三个元素，一共有 2 3 = 8 2^3=8 23=8个子集，将0到 8 8 8转化为3位二进制分别为：000,001,010,011,100,101,110,111。1代表有当前元素，0代表没有，答案就对应为`[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]`。

### 算法实现 ###

def subsets(self, nums: List[int]) -> List[List[int]]:
        res = [[]]
        lenth = len(nums)
        for i in range(1, 2 ** lenth):
            temp = []
            s = "{:b}".format(i)[::-1]
            print(s)
            for x in range(len(s)):
                if s[x] == '1':
                    temp.append(nums[x])
            res.append(temp)
        return res

### 执行结果 ###

**执行结果** : 通过  
**执行用时** : 36 ms, 在所有 Python3 提交中击败了81.17%的用户  
**内存消耗** : 13.7 MB, 在所有 Python3 提交中击败了5.72%的用户  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]

### 复杂度分析 ###

*  时间复杂度： O ( N × 2 N ) \\mathcal\{O\}(N \\times 2^N) O(N×2N)，生成所有的子集，并复制到输出列表中。
 *  空间复杂度： O ( N × 2 N ) \\mathcal\{O\}(N \\times 2^N) O(N×2N)，存储所有子集，共  n n n 个元素，每个元素都有可能存在或者不存在。

## 想法二：将二进制的想法直接运用（官方递归） ##

我们思考一下为什么子集的数量会是，其实是每次增加一个元素，子集的数量就会翻一倍，而多出来的这一倍其实是原来的每一个子集加上了该元素，举个栗子就明白了。

例如`[1]`的子集是`[],[1]`；  
多出一个元素`[1,2]`的子集是`[][1]`和多一倍的`[2],[1,2]`；  
再多一个元素`[1,2,3]`的子集是`[],[1],[2],[1,2]`和多一倍的`[3],[1,3],[2,3],[1,2,3]`。

### 算法实现 ###

def subsets(self, nums: List[int]) -> List[List[int]]:
        res = [[]]
        lenth = len(nums)
        for i in range(lenth):
            res.extend([x + [nums[i]] for x in res])
        return res

### 执行结果 ###

![在这里插入图片描述][20200414123139190.png]

### 复杂度分析 ###

## 小结 ##

题目很有意思，通过二进制的转化有了很多想法，官方的题解法大同小异，需要注意的是在用列表复制的时候会遇到深浅拷贝的问题，这里提供一篇[解答的博客][Link 1]。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]: /images/20230528/fde6f65abd8248d3a786f1a9b2969e19.png
[20200414123139190.png]: /images/20230528/67603ccdf5c846e89ae563ccf1f7028e.png
[Link 1]: https://www.cnblogs.com/pyramid1001/p/5844905.html