78. 子集

https://leetcode-cn.com/problems/subsets/

解法一：

两种写法：

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        self.res = []
        tmpList = []
        for i in range(len(nums)+1):  #len+1轮循环，每次输出长度为i的所有组合
            self.backtrack(nums, tmpList, i, 0)
        return self.res

    def backtrack(self, nums, tmpList, k, start):    #从nums的start位置开始取
        if len(tmpList) == k:
            self.res.append(list(tmpList))
        for i in range(start, len(nums)):
            tmpList.append(nums[i])
            self.backtrack(nums, tmpList, k, i + 1)    #下一层递归start为i+1
            tmpList.pop()

由22.括号生成的回溯改写得到启发：

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        self.res = []
        tmpList = []
        for i in range(len(nums)+1):  #len+1轮循环，每次输出长度为i的所有组合
            self.backtrack(nums, tmpList, i, 0)
        return self.res

    def backtrack(self, nums, tmpList, k, start):
        if len(tmpList) == k:
            self.res.append(list(tmpList))
        for i in range(start, len(nums)):    #tmp的修改直接写在递归里
            self.backtrack(nums, tmpList+[nums[i]], k, i + 1)

解法二：迭代

类似 17.电话号码的字母组合

解法一

对于这种无重复元素的子集，可以用迭代法生成笛卡尔积

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = [[]]
        for n in nums:
            newRes = list(res)    #复制一份结果集，注意不能直接=
            for r in res:    #结果集中每个元素，加入新num
                newRes += [r + [n]]
            res = newRes    #更新
        return res

可以简化为

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