動機

backtrack與重複

filter與next是不是有bug阿

Problem

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:

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

Example 2:

Input: nums = [0]Output: [[],[0]]

 

Constraints:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10

Sol

把重複的視為一體沒有重複的問題了

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        def dfs(nums):
            if not nums:
                return [[]]
            elif len(nums) == 1 or nums[0] != nums[1]:
                ret = dfs(nums[1:])
                return ret+[s+[nums[0]] for s in ret]
            else:
                i = 1
                while i < len(nums) and nums[i-1] == nums[i]:
                    i += 1
                # i = next(filter(lambda ix: nums[ix[0]-1] != nums[ix[0]], enumerate(nums)),[len(nums),None])[0]
                # [1,1,2,2] 時 i 會是0 !??
                ret = dfs(nums[i:])
                ss = [[nums[0]]*n for n in range(1,i+1)]
                return ret + sum([[s+x for x in ret] for s in ss],[])
        return dfs(sorted(nums))