每日一题:LeetCode-78. 子集
刷题使我快乐,满脸开心.jpg
来源:力扣(LeetCode)
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题目
给你一个整数数组 nums
,数组中的元素 互不相同
。返回该数组所有可能的子集(幂集)。
解集 不能
包含重复的子集。你可以按 任意顺序
返回解集。
示例 1:
复制代码
示例 2:
复制代码
提示:
1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums
中的所有元素互不相同
思路
子集问题也算是比较经典的题目了,回溯也好,想象成二进制遍历也罢,但终归都是对于结果集各种可能性
的尝试和探索
回溯思路
回溯思路就是将结果整构成0长度子集
为根节点,1长度子集
为第一层子节点,以此类推而成的一棵树,而在这棵树上,要做的就是用dfs
或者bfs
的搜索方法去探究,不过bfs
的判重逻辑可能会比较麻烦,所以感觉还是dfs
更好实现一些。当然,对于树,那就需要进行剪枝,剪出重复的答案即可
二进制思路
将数组的每一个元素对应二进制数字的一个位,那么从全0
到全1
的二进制数字,正好就是所有元素的选与不选的可能性集合了,也就是子集
至此,上代码
代码
复制代码
欢迎关注公众号查看更多题目~
版权声明: 本文为 InfoQ 作者【半亩房顶】的原创文章。
原文链接:【http://xie.infoq.cn/article/71edbd93ea44062668bf03cb8】。文章转载请联系作者。
评论