Leetcode 90:子集 II(最详细的解法!!!)
in leetcode with 0 comment

Leetcode 90:子集 II(最详细的解法!!!)

in leetcode with 0 comment

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

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

示例:

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

解题思路

这个问题是之前问题Leetcode 78:子集(最详细的解法!!!)的扩展。我们用之前的解法会出现这样的问题,[1,2]会出现两次,因为我们有两个2。最简单的思路就是添加一个判断if tmp not in result,并且我们要对nums排序,为什么?为了避免出现这种情况

1,4,1
4,1,1

这两种在这个问题中是一种情况,但是在判断[1,4,1]==[4,1,1],两者是不相同的。

class Solution:
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if not nums:
            return [[]]

        nums.sort()
        result = self.subsetsWithDup(nums[1:])
        return result + [[nums[0]] + s for s in result if [nums[0]] + s not in result]

可想而知,这种做法显然不是最快的。实际上我们这里可以参考 Leetcode 40:组合总和 II(最详细的解法!!!)的回溯法写法,再循环中添加一步判断即可(如果当前元素和其前一个元素相同,我们就不将它加入到当前的结果中去)。

class Solution:
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        result = list()
        self._subsetsWithDup(nums, 0, list(), result)
        return result
    
    def _subsetsWithDup(self, nums, index, path, result):
        result.append(path)
        for i in range(index, len(nums)):
            if index < i and nums[i] == nums[i - 1]:# add
                continue
            self._subsetsWithDup(nums, i + 1, path + [nums[i]], result)

需要注意的是条件中的index < i and nums[i] == nums[i - 1],这保证了每次只会添加相同元素中的一个。

另外,我们也可以这么考虑,对于k个重复元素,我们考虑添加0~k次重复元素的情况,所以有k次地柜调用的过程。那么代码可以写成:

class Solution:
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        result = list()
        self._subsetsWithDup(nums, 0, list(), result)
        return result
    
    def _subsetsWithDup(self, nums, index, path, result):
        if index == len(nums):
            result.append(path[::])
            return 

        k = index
        while k < len(nums) and nums[k] == nums[index]:
            k += 1

        self._subsetsWithDup(nums, k, path, result) #不添加相同元素
        for i in range(index, k): #添加1~k-index个相同元素
            path.append(nums[i])
            self._subsetsWithDup(nums, k, path, result)
        for i in range(index, k): #弹出末尾所有相同元素
            path.pop()

同样的,对于递归可以解决的问题,我们都应该思考是不是可以通过迭代解决。

class Solution:
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        result = [[]]
        for i in range(len(nums)):
            if i == 0 or nums[i] != nums[i - 1]:
                start = len(result)
            
            end = len(result)
            for j in range(end - start, end):
                result += [result[j] + [nums[i]]]
        return result

我这里的迭代写法使用了一个小trick

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses