leetcode 90 子集 II
z
 2019-07-05 15:13:52  

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

说明：解集不能包含重复的子集。

示例:

1
2
3
4
5
6
7
8
9
10
输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

  • dfs

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution(object):
        def subsetsWithDup(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
             ans = []
             nums.sort()
             def dfs(ans, t, nums, start):
                 if  t not in ans:
                     ans.append(copy.copy(t))
                    
                 for i in range(start, len(nums)):
                     if i > start and nums[i] == nums[i-1]:
                         continue    
                     t.append(nums[i])
                     dfs(ans, t, nums, i+1)
                     t.pop()
                
             dfs(ans, [], nums, 0)
             return ans

  • 不排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution(object):
        def subsetsWithDup(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            counter = collections.Counter(nums)
            ans = [[]]
            for n in counter:
                temp = copy.copy(ans)
                for i in ans:
                    temp.extend(i + [n]* c for c in range(1, counter[n]+1))
                ans = copy.copy(temp)
            return ans