leetcode练习——回溯算法（子集）

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

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

精彩解法：https://leetcode-cn.com/problems/subsets/solution/hui-su-suan-fa-by-powcai-5/

解法一：库函数（36ms/14.9MB）

• itertools.combinations()

创建一个迭代器，返回iterable中所有长度为r的子序列，返回的子序列中的项按输入iterable中的顺序排序 (不带重复).

r 指定生成排列的元素的长度，如果不指定，则默认为可迭代对象的元素长度。

对应组合概念。

>>> from itertools import combinations
>>>
>>> list(combinations('ABC', 2))
[('A', 'B'), ('A', 'C'), ('B', 'C')]
           

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
           

解法二：迭代（36ms/15.2MB)

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

解法三：递归(回溯算法)（36ms/15MB）

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

力扣链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xv67o6/