【python-leetcode78-子集】子集

给定一组不含重复元素的整数数组?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]]

此时，别忘了我们还有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）

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!