子寒的博客
0%

leetcode90 subsetsII 解题报告

发表于 分类于

英文原题

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example

1
2
Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

分析

    类似求全排列，用递归的思路，题目要求同样数字不同排序也只能算一个，比如[1,2]和[2,1]就是一个。所以为了去重我们要先给数组排序，在递归中遇到相同的数字只算一个。

python 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        
        def dfs(path, index):
            if path not in res:
                res.append(path)
            for i in range(index, len(nums)):
                if i > index and nums[i] == nums[i-1]:
                    continue
                dfs(path+[nums[i]], i+1)
        
        dfs([], 0)
        return res

也有更简单的方法

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = [[]]
        nums.sort()
        
        for num in nums:
            for i in range(len(res)):
                if res[i] + [num] not in res:
                    res.append(res[i]+[num])
        
        return res