動機
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))