[数据结构与算法]LeetCode 90. 子集 II

1、题目

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

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

示例 1：

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

2、解答

这道题和之前78题子集那题一样的解法，就是多了一点需要注意，可以有重复的元素，所以需要对子集进行去重，两种去重方法，一种是在子集获得后插入到结果集的时候去重，一种是先不管重复的子集，获得所有结果后再去重，这个时候可以考虑转set。但是为了方便起见，还是在前面就去重，为了去重就得考虑先排序，这样是为了去重方便。

• 暴力法：拓展法，就是遍历nums，然后把元素加入到结果集中的每一个元素中形成新的子集元素，然后看看这个子集是不是已经出现过，出现过就不插入结果集中。

• 深度优先：遍历nums元素，每次以形成子集长度/深度优先，当形成的子集长度不超过nums长度且不是重复子集时，就插入到结果列表中。

• 广度优先：以子集可能的长度来遍历nums。

代码实现：

import copy

class Solution(object):
    def subsetsWithDup(self, nums):
        """
        暴力法：先对nums进行排序，然后再遍历每个元素，添加进入
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        res.append([])
        nums.sort()
        for i in nums:
            res += [j+[i] for j in res if j+[i] not in res]
        return res

    def subsetsWithDup2(self, nums):
        """
        DFS:深度优先
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        nums.sort()
        self.dfs(nums, res, 0, [])
        return res

    def dfs(self, nums, res, begin, tmp_list):
        if len(tmp_list)<=len(nums) and tmp_list not in res:
            res.append(copy.deepcopy(tmp_list))

        for i in range(begin, len(nums)):
            tmp_list.append(nums[i])
            self.dfs(nums, res, i+1, tmp_list)
            tmp_list.pop()

    def subsetsWithDup3(self, nums):
        """
        BFS:广度优先
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        nums.sort()
        for i in range(0, len(nums)+1):
            self.bfs(nums, res, 0, i, [])
        return res


    def bfs(self, nums, res, begin, length, tmp_list):
        if len(tmp_list)==length and tmp_list not in res:
            res.append(copy.deepcopy(tmp_list))

        for i in range(begin, len(nums)):
            tmp_list.append(nums[i])
            self.bfs(nums, res, i+1, length, tmp_list)
            tmp_list.pop()