90. 子集 II

90. 子集 II

问题

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

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

示例:

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

分析

相对78. 子集，需要上来对nums进行排序，然后对当前的path进行判断是否已经存在在res中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        def backtrack(index): 
            if index > self.length: return 
            if path in res: return
            res.append(path.copy()) 
            for i in range(index, self.length): 
                path.append(nums[i])
                backtrack(i + 1)
                path.pop() 

        res = []
        path = []
        nums.sort()
        self.length = len(nums)
        backtrack(0)
        return res

思考

  1. 能否进一步降低时间复杂度？