【python-leetcode78-子集】子集_python

概述给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。示例: 输入: nums = [1,2,3]输出:[ [3], [1], [2]

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

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

示例:

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

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

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

第一步：res=[[]]

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

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

第四步：res=[[],[3],[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  res]        return res

方法二：python中自带的库

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

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

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

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

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

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

输出：[[],[3]]

捋一捋过程吧：

首先是res=[]

执行helper(0,3])

然后res=[[]]

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

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

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

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

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

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