###### tags: `Leetcode` `medium` `backtracking` `python`

# 47. Permutations II

## [題目連結:] https://leetcode.com/problems/permutations-ii/

## 題目:
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]]

## 解題想法:
兄弟題目: [46. Permutations](/YKgBx4aeRFyb5g92rTknWg)

* 此題要求，給一數組，可能有含重複元素，求其所有排列組合(組合不能重複)

* 解題:
* 需先將數組排序好
* visited[]: 紀錄該位置是否訪問過
* 進入遞迴:
* 若當前位置已經拜訪過了:continue
* 若與前一個位置的數相同，且前一個位置還沒拜訪過，則當前不能先拜訪:continue

## Python:

class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        self.res=[]
        visited=[False]*len(nums) #紀錄該位置是否訪問過
        nums.sort() #先排序 避免重複
        self.dfs(nums,[],visited)
        return self.res
    def dfs(self,nums,path,visited):
        if len(path)==len(nums):
            self.res.append(path)
            return 
        for i in range(len(nums)):
            #若當前位置已經拜訪過了，跳過
            if visited[i]:
                continue
            #若與前一個位置的數相同，且前一個位置還沒拜訪過，則當前不能先拜訪
            if i>0 and nums[i]==nums[i-1] and not visited[i-1]:
                continue
            visited[i]=True
            self.dfs(nums,path+[nums[i]],visited)
            visited[i]=False
            
if __name__ == '__main__':
    result = Solution()
    nums = [0,1,0,0,9]
    ans = result.permuteUnique(nums)
    print(ans,len(ans))