Leetcode 78. 子集 and 90. 子集 II

78. 子集

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

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

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

排列问题，一般都可以用深搜做，当然广搜也可以，这里给出三种解法。

深搜1

构建一棵二叉树，每层判断是否要放入nums[i]，由根节点到叶子节点的路径构成一个子集。

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def dfs(path, depth):
            if depth == len(nums):
                res.append(path[:])
                return 
            path.append(nums[depth])
            dfs(path, depth + 1)
            path.pop()

            dfs(path, depth + 1)
        res = []
        dfs([], 0)
        return res

深搜2

每层从剩下的可选数字中选择一个放入，从第0层往下，第i层代表含有i个元素的子集，所以每层要保存到答案中。为了避免重复，先对数组排序，只选择更大的元素放入（保证升序）。

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

动态规划

由可选的数字各不相同，每加入一个数字，就将未加入前的子集的子集数量翻了个倍，因此可以采用dp递推，从遍历角度也像是BFS。

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
        

90. 子集 II

相比子集1就多了一个条件，数组中存在重复元素，需要我们做到去重操作。同样给出dfs与dp两种解法。

dfs

同层的数字选择中，不应该出现重复元素。因此如果该层的数字选择与上次相同，就跳过。

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        def dfs(path, index):
            res.append(path[:])
            for i in range(index, len(nums)):
                if i > index and nums[i - 1] == nums[i]:
                    continue
                path.append(nums[i])
                dfs(path, i + 1)
                path.pop()
        nums.sort()
        res = []
        dfs([], 0)
        return res

dp

采用动态规划依旧要去重，通过排序将相同元素挨在一起，可以发现，如果这次要放入的元素与上次相同，只需要增加1/2的数量（否则出现重复），若上上次也是相同的数字，则增加1/3的子集数，如此类推。

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = [[]]
        nums.sort()
        count = 2 
        for i in range(len(nums)):
            if i > 0 and nums[i - 1] == nums[i]:
                for j in range(len(res) - len(res) // count, len(res)):
                    res.append(res[j] + [nums[i]])
                count += 1
            else:
                for j in range(len(res)):
                    res.append(res[j] + [nums[i]])
                count = 2

        return res
                

也可以用new_subsets记录这次新增加的子集，下次遇到重复元素，只需在nwe_subsets的基础上做增加。

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = [[]]
        nums.sort()
        for i in range(len(nums)):
            if i > 0 and nums[i - 1] == nums[i]:
                new_subsets = [subset + [nums[i]] for subset in new_subsets]
            else:
                new_subsets = [subset + [nums[i]] for subset in res]
            res += new_subsets
        return res