每日一题:LeetCode-78. 子集

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










评论