leetcode 90 子集 ii

给定一个可能包含重复元素的整数数组 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 (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 (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