​LeetCode刷题实战78：子集

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！

今天和大家聊的问题叫做 子集，我们先来看题面：

https://leetcode-cn.com/problems/subsets/

Given a set of distinct integers, nums, return all possible subsets (the power set). Note: The solution set must not contain duplicate subsets.

题意

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

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

样例

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

解题

https://www.cnblogs.com/techflow/p/13151068.html

二进制组合

我们可以从子集的特点入手。我们之前学过，一个含有n个元素的子集的数量是

。这个很容易想明白，因为n个元素，每个元素都有两个状态，选或者不选。并且这n个元素互相独立，也就是说某个元素选或者不选并不会影响其他的元素，所以我们可以知道一共会有

种可能。

我们也可以从组合数入手，我们令所有子集的数量为S，那么根据上面我们用组合求解的解法，可以得到：

两者的结果是一样的，说明这个结论一定是正确的。

不知道大家看到n个元素，每个元素有两个取值有什么想法，如果做过的题目数量够多的话，应该能很快联想到二进制。因为在二进制当中，每一个二进制位就只有0和1两种取值。那么我们就可以用n位的二进制数来表示n个元素集合取舍的状态。n位二进制数的取值范围是

，所以我们用一重循环去遍历它，就相当于一重循环遍历了整个集合所有的状态。

这种技巧我们也曾经在动态规划状态压缩的文章当中提到过，并且在很多题目当中都会用到。所以建议大家可以了解一下，说不定什么时候面试就用上了。

根据这个技巧， 我们来实现代码就非常简单了。

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ret = []
        n = len(nums)
        # 遍历所有的状态
        # 1左移n位相当于2的n次方
        for s in range(1 << n):
            cur = []
            # 通过位运算找到每一位是0还是1
            for i in range(n):
                # 判断s状态在2的i次方上，也就是第i位上是0还是1
                if s & (1 << i):
                    cur.append(nums[i])
            ret.append(cur[:])
            
        return ret

从代码来看明显比上面的解法短得多，实际上运行的速度也更快，因为我们去掉了所有多余的操作，我们遍历的每一个状态都是正确的，也不用考虑重复元素的问题。

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力。

上期推文：

LeetCode40-60题汇总，速度收藏！

LeetCode刷题实战61：旋转链表

LeetCode刷题实战62：不同路径

LeetCode刷题实战63：不同路径 II

LeetCode刷题实战64：最小路径和

LeetCode刷题实战66：加一

LeetCode刷题实战67：二进制求和

LeetCode刷题实战68：文本左右对齐

LeetCode刷题实战69：x 的平方根

LeetCode刷题实战70：爬楼梯

LeetCode刷题实战71：简化路径

LeetCode刷题实战72：编辑距离

LeetCode刷题实战73：矩阵置零

LeetCode刷题实战74：搜索二维矩阵

LeetCode刷题实战75：颜色分类

LeetCode刷题实战76：最小覆盖子串

LeetCode刷题实战77：组合