​LeetCode刷题实战78：子集

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

今天和大家聊的问题叫做 子集&＃xff0c;我们先来看题面&＃xff1a;

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&＃xff0c;返回该数组所有可能的子集&＃xff08;幂集&＃xff09;。

说明&＃xff1a;解集不能包含重复的子集。

样例

输入: nums &＃61; [1,2,3]
输出:
[[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]
]


解题

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

二进制组合

我们可以从子集的特点入手。我们之前学过&＃xff0c;一个含有n个元素的子集的数量是。这个很容易想明白&＃xff0c;因为n个元素&＃xff0c;每个元素都有两个状态&＃xff0c;选或者不选。并且这n个元素互相独立&＃xff0c;也就是说某个元素选或者不选并不会影响其他的元素&＃xff0c;所以我们可以知道一共会有种可能。

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

两者的结果是一样的&＃xff0c;说明这个结论一定是正确的。

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

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

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

class Solution:def subsets(self, nums: List[int]) -> List[List[int]]:ret &＃61; []n &＃61; len(nums)# 遍历所有的状态# 1左移n位相当于2的n次方for s in range(1 <

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

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

上期推文&＃xff1a;

LeetCode40-60题汇总&＃xff0c;速度收藏&＃xff01;

LeetCode刷题实战61&＃xff1a;旋转链表

LeetCode刷题实战62&＃xff1a;不同路径

LeetCode刷题实战63&＃xff1a;不同路径 II

LeetCode刷题实战64&＃xff1a;最小路径和

LeetCode刷题实战66&＃xff1a;加一

LeetCode刷题实战67&＃xff1a;二进制求和

LeetCode刷题实战68&＃xff1a;文本左右对齐

LeetCode刷题实战69&＃xff1a;x 的平方根

LeetCode刷题实战70&＃xff1a;爬楼梯

LeetCode刷题实战71&＃xff1a;简化路径

LeetCode刷题实战72&＃xff1a;编辑距离

LeetCode刷题实战73&＃xff1a;矩阵置零

LeetCode刷题实战74&＃xff1a;搜索二维矩阵

LeetCode刷题实战75&＃xff1a;颜色分类

LeetCode刷题实战76&＃xff1a;最小覆盖子串

LeetCode刷题实战77&＃xff1a;组合