動機

46的follow-up

Problem

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

 

Example 1:

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

Example 2:

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

 

Constraints:

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

Sol

在同一層不要展開已經展開過的數字

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def dfs(nums,acc):
            if not nums:
                return [acc]
            else:
                seen,ret = set(), []
                for k in range(len(nums)):
                    if nums[k] not in seen:
                        seen.add(nums[k])
                        ret += dfs(nums[:k]+nums[k+1:],acc+[nums[k]])
                return ret
        return dfs(nums,[])