Permutations II

题目

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

For example,
[1,1,2]have the following unique permutations:

[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

思路分析

这道题跟permutations I的最大区别是这道题的input数组中包含重复的元素。那么相对于permutations I就要在多一层去重，所以有两层去重

第一层去重：类似于permutations I，避免同一个元素在排列数组中被多次使用，通过visited数组来实现调用递归函数的时候不要再使用上一层使用的数字

第二层去重：因为输入数组中有重复的元素，所以当数字第一次出现的时候相应的排列数组都已经放在result中，当同样的数字第二次出现的时候就没有必要在做相同的操作而直接pass即可。这一层去重一般是通过对原始数组排序，然后判断当前的元素是不是与上一个元素相同来完成的。但是这道题除了这两个条件以外，还有多一个判断条件，不然的话有些valid的排列数组也被filer掉了。这个条件就是判断前一个元素是不是被visited过，如果visited=True，说明现在正在查找上一个元素开始的所有排列数组，那么这个元素虽然与上个元素一样，但是也要放在排列数组中；如果visited=False，说明之前的元素已经查找完了所有以它开始的排列数组，因为当前元素与之前元素一样，所以这个时候就没有必要再为当前元素查找排列数组了。

class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        def dfs(nums, length, visited, path, result):
            if length == 0:
                result.append(path)
                return
            for i in range(0, len(nums)):
                if visited[i]: continue
                if i>0 and nums[i] == nums[i-1] and not visited[i-1]: continue    <<<<<<<<
                visited[i] = True
                dfs(nums, length-1, visited, path+[nums[i]], result)
                visited[i] = False
        len_nums = len(nums)
        result = []
        visited = len_nums * [False]
        dfs(sorted(nums), len_nums, visited, [], result)
        return result