写点什么

每日一题:LeetCode-78. 子集

作者:半亩房顶
  • 2023-12-06
    北京
  • 本文字数:920 字

    阅读完需:约 3 分钟

每日一题:LeetCode-78. 子集

刷题使我快乐,满脸开心.jpg


题目

给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。


解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。


示例 1:


输入:nums = [1,2,3]输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
复制代码


示例 2:


输入:nums = [0]输出:[[],[0]]
复制代码


提示:


  • 1 <= nums.length <= 10

  • -10 <= nums[i] <= 10

  • nums 中的所有元素 互不相同

思路

子集问题也算是比较经典的题目了,回溯也好,想象成二进制遍历也罢,但终归都是对于结果集各种可能性的尝试和探索

回溯思路

回溯思路就是将结果整构成0长度子集为根节点,1长度子集为第一层子节点,以此类推而成的一棵树,而在这棵树上,要做的就是用dfs或者bfs的搜索方法去探究,不过bfs的判重逻辑可能会比较麻烦,所以感觉还是dfs更好实现一些。当然,对于树,那就需要进行剪枝,剪出重复的答案即可


二进制思路

将数组的每一个元素对应二进制数字的一个位,那么从全0全1的二进制数字,正好就是所有元素的选与不选的可能性集合了,也就是子集



至此,上代码

代码

func subsets(nums []int) [][]int {    n := len(nums)    res := make([][]int, 0)
// 代表临时结果 set := make([]int, 0) var dfs func(n int) dfs = func(i int) { // 每次进入时均代表着一种可能行,所有可能性构成子集 // 必须要做一次数组深拷贝,不然就是slice典型的问题了 res = append(res, append([]int{}, set...)) // 遍历到最后也就是找寻完当前可能性下的所有子集了 if i == n { return } // 从之前未选过的地方开始选择,剪去重复子集 for j := i; j < n; j++ { // 代表去寻找选择当前数字的可能结果集 set = append(set, nums[j]) dfs(j + 1) // 再次进入循环时也就代表去寻找未选择当前数字的可能子集 set = set[:len(set)-1] } } dfs(0) return res}
复制代码



欢迎关注公众号查看更多题目~


发布于: 刚刚阅读数: 4
用户头像

半亩房顶

关注

人生那么长,能写多少bug? 2018-11-16 加入

我希望,自己永远是自己。我希望,远离bug。

评论

发布
暂无评论
每日一题:LeetCode-78. 子集_面试_半亩房顶_InfoQ写作社区