78. 子集

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

解法一：迭代法

初始化一个包含空集的结果集，然后遍历nums，用nums不断拓展已有的集合。

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

解法二：回溯

按子集的长度逐层递归回溯，root为空集，第n层为长度为n-1个元素构成的子集。

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        """Build subsets with length 0, 1...len(nums)."""
        res = []
        for i in range(len(nums)):
            self.bc(nums, i, 0, [], res)
        return res
    def bc(self, nums, length, start, cur, res):
        """
        Use backtracking to build subsets of nums.
        Args:
            nums (List[int]): the provided number list
            length (int): the target length of the current subset
            start (int): the index of the first number of the subset in nums
            cur (List[int]): the current subset
            res (List[int]): the result list
        Returns:
            None
        """
        if len(cur) == length:
            res.append(cur[:])
            return
        for i in range(start, len(nums)):
            cur.append(nums[i])
            self.bc(nums, length, i + 1, cur, res)
            cur.pop()

解法三：DFS

从第一个元素开始深度遍历，将经过的路径保存。当前层的下一步只能访问当前元素后面的元素。

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