90.md

题目地址

https://leetcode-cn.com/problems/subsets-ii/

解答1

class Solution:
    def __init__(self):
        self.result_all = None

    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        """
            子集II(非最优解)

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

            输入: [1,2,2]
            输出:
            [
              [2],
              [1],
              [1,2,2],
              [2,2],
              [1,2],
              []
            ]
        """
        self.result_all = [[]]
        nums = sorted(nums)
        self.dfs(nums, 0, 0, [])
        return self.result_all

    def dfs(self, nums, n, start, result):
        if n == len(nums):
            return

        pre_num = None
        for i in range(start, len(nums)):
            if pre_num == nums[i]:
                continue
            pre_num = nums[i]
            result.append(nums[i])
            self.result_all.append(result[:])
            self.dfs(nums, n + 1, i + 1, result)
            result.pop()

        return

解答2

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        """
            子集II(非最优解)

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

            输入: [1,2,2]
            输出:
            [
              [2],
              [1],
              [1,2,2],
              [2,2],
              [1,2],
              []
            ]
        """
        m = {}
        for i in nums:
            if i in m:
                m[i] += 1
            else:
                m[i] = 1

        res = [[]]
        for k, v in m.items():
            nextSet = [[k] * i for i in range(v + 1)]
            res = [pre + pos for pre in res for pos in nextSet]
        return res

解答3

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        """
            子集II

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

            输入: [1,2,2]
            输出:
            [
              [2],
              [1],
              [1,2,2],
              [2,2],
              [1,2],
              []
            ]
        """
        if len(nums) == 0:
            return [[]]
        nums.sort()
        res = []
        length = len(nums)
        self.lastadd = 0

        # 原来76模式
        def recursion(num: int, cur_len: int):
            if cur_len == 1:
                res.append([])
                res.append([num])
                self.lastadd = 1
            else:
                sub = res[:]
                for item in sub:
                    res.append(item + [num])
                self.lastadd = len(res) - len(sub)

        # 重复元素部分
        def recursion2(num: int, cur_len: int):
            sub = res[len(res) - self.lastadd:]
            for item in sub:
                res.append(item + [num])

        # 依据是否重复 来通过不同函数
        for index, num in enumerate(nums):
            if index > 0 and num == nums[index - 1]:
                recursion2(num, index + 1)
            # 不同的数进行的是 原来的操作
            else:
                recursion(num, index + 1)

        return res

解答4

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        """
            子集II(非最优解)

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

            输入: [1,2,2]
            输出:
            [
              [2],
              [1],
              [1,2,2],
              [2,2],
              [1,2],
              []
            ]
        """
        from functools import reduce
        import collections
        return reduce(lambda x, i: [a + [i[0]] * j for j in range(i[1] + 1) for a in x],
                      collections.Counter(nums).items(), [[]])