本周题目难度'Medium',使用语言'Python'

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

思路：这题目是第五十九题的延伸，所以做出第五十九题，只要加两行代码（一行排序，一行判断是否重复）就ok了，思路是和第五十九题一样的，一样的代码我就不注释了，只注释改变的地方：

class Solution:
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        def dfs(begin, end, k, temp, result, nums):
            if k: 
                for i in range(begin,end):
                    if (end - i + 1 < k): break 
                    temp.append(nums[i-1])
                    dfs(i + 1, end, k - 1, temp, result, nums)
                    del temp[-1]
            else:
                # 判断是否已经加过了，加过就不处理了，没加过就加进去
                if not temp in result:
                    one = []
                    for i in temp:
                        one.append(i)
                    result.append(one)
        result = [[]]
        k = len(nums)
        # 排序，方便去重
        nums.sort()
        while k:
            dfs(1, len(nums)+1, k, [], result, nums)
            k -= 1
        return result

效率一般，再看看效率高的

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

版权声明：本文为 Crazy Steven 原创出品，欢迎转载，转载时请注明出处!