Leetcode 90.子集II

Posted on |

90.子集II

题目

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

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

1
2
3
4
5
6
7
8
9
10
11
12
示例:

输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

方法

方法1：回溯法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res=[]
        nums=sorted(nums)
        self.backtrack(nums,res,[],0)
        return res

    def backtrack(self,nums,res,temp,start):
        res.append(list(temp))
        for i in range(start,len(nums)):
            if i>start and nums[i]==nums[i-1]:    # skip duplicates
                continue
            temp.append(nums[i])
            self.backtrack(nums,res,temp,i+1)
            temp.pop()
# backtrack([1, 2, 2], [], [], 0)
# backtrack([1, 2, 2], [[]], [1], 1)
# backtrack([1, 2, 2], [[], [1]], [1, 2], 2)
# backtrack([1, 2, 2], [[], [1], [1, 2]], [1, 2, 2], 3)
# pop:  2
# --------------------
# pop:  2
# --------------------
# pop:  1
# --------------------
# backtrack([1, 2, 2], [[], [1], [1, 2], [1, 2, 2]], [2], 2)
# backtrack([1, 2, 2], [[], [1], [1, 2], [1, 2, 2], [2]], [2, 2], 3)
# pop:  2
# --------------------
# pop:  2
# --------------------
# [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]