专栏首页数据分析与挖掘【python-leetcode78-子集】子集

【python-leetcode78-子集】子集

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

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

示例:

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

由于是子集的第一题,暂时还没有套路。

方法一:直接看过程,假设我们现在有一个存储结果的数组res=[[]],nums=[1,2,3]

第一步:res=[[]]

第二步:res=[[],[1]]

第三步:res=[[],[2],[1],[1,2]]

第四步:res=[[],[3],[2],[2,3],[1],[1,3],[1,2,3]]

也就是说每次取出res中里面的一维数组,然后将当前nums中的数加进去,再和原来的res相加即可

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res=[[]]
        for num in nums:
            res=res+[tmp+[num] for tmp in res]
        return res

方法二:python中自带的库

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        for i in range(len(nums)+1):
            for tmp in itertools.combinations(nums, i):
                res.append(tmp)
        return res

会单独再写一篇记录一下itertools的用法

方法三:回溯,解决子集这种问题的话一般就是这种方法了。不过不好理解。

回溯法的核心就是试错,碰到不符合要求的就返回。

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        global res
        res=[]
        self.helper(0,[],nums)
        return res
    def helper(self,i,tmp,nums):
        res.append(tmp)
        for j in range(i,len(nums)):
            self.helper(j+1,tmp+[nums[j]],nums)
        

其中的核心是遍历的下标以及将tmp带入到递归中。

输出:[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]

捋一捋过程吧:

首先是res=[]

执行helper(0,[],[1,2,3])

然后res=[[]]

这里有个for j in range(0,3)

执行helper(1,[]+[1],[1,2,3])

然后res=[[],[1]]

这里有个for j in range(1,3)

执行helper(2,[1]+[2],[1,2,3])

然后res=[[],[1],[1,2]]

依次类推之后我们就有[[],[1],[1,2],[1,2,3]]

此时,别忘了我们还有for循环中没有循环完

for j in range(0,3)

for j in range(1,3)

for j in range(2,3)

与子集有关的题目还有:

39. 组合总和

40. 组合总和 II

46. 全排列

47. 全排列 II

78. 子集

90. 子集 II

参考:

作者:powcai 链接:https://leetcode-cn.com/problems/subsets/solution/hui-su-suan-fa-by-powcai-5/ 来源:力扣(LeetCode)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • django-URL反向解析Reverse(九)

    reverse(viewname,urlconf=None,args=None,Kwargs=None,current_app=None)

    绝命生
  • c++多态实例之电脑组装

    绝命生
  • springmvc之CookieValue注解

    绝命生
  • deep learning paper

    Some high-light papers are selected just for reference, most of them are associa...

    点云PCL博主
  • Python排序算法[二]:测试数据的迷雾散去

    在上一篇文章《Python 排序算法[一]:令你茅塞顿开,却又匪夷所思》中我们学习了排序算法中比较费时间的三种:冒泡排序、选择排序、插入排序。并且在测试过程中发...

    崔庆才
  • 一文尽览推荐系统模型演变史

    4. 整理此文的目的是给大家一个清晰的脉络,可当作一篇小小综述。从信息过载概念的提出到推荐系统的起源,从前深度学习时代的推荐系统到劲头正热的深度推荐系统,再到最...

    张小磊
  • 误差分析指标计算之matlab实现

    感谢关注matlab爱好者公众号!如果公众号文章对您有帮助,别忘了点击分享和“在看”哦!若您对公众号有什么意见或建议,请在公众号中回复或在任意文章底部留言!

    matlab爱好者
  • Python-接口自动化(七)

    1、requests是用python语言编写,属于第三方库,基于urllib,采用Apache2 Licensed开源协议的HTTP库,它比urllib更加方便...

    py3study
  • es6 -- Iterator 和 for...of 循环

    JavaScript 原有的表示“集合”的数据结构,主要是数组(Array)和对象(Object),ES6 又添加了Map和Set。这样就有了四种数据集合,用户...

    小蔚
  • 第23章、存储程序和视图

    本章讨论存储的程序和视图,这些数据库对象是根据存储在服务器上供以后执行的SQL代码定义的数据库对象。

    幺鹿

扫码关注云+社区

领取腾讯云代金券