leetcode78. 子集

思路一

回溯法

代码

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

思路二

迭代，[a, b, c]的子集由两部份组成，一部分是[b, c]子集的每个元素都加上a，一部分是[b, c]的子集

代码

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        if not nums:
            return [[]]
        else:
            first_element = [nums.pop(0)]
            sub = self.subsets(nums)
            res = [first_element + i for i in sub] + sub
        return res

思路三

用库函数itertools.combinations

 def subsets(self, nums: List[int]) -> List[List[int]]:
     from itertools import combinations
     return sum([list(combinations(nums, i)) for i in range(len(nums) + 1)], [])