47. Permutations

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]
]

Solutions:

Basic idea is exactly the same as Permutations problem one. Use dfsVisit to go through all possible combinations of permutations.

难点是，dfsVisit里的for loop 开始和结束 index，以及何时进入下一轮recursion的condition判断。

以后的建议做法是，先写出 high level，然后跟面试官一起想出需要的conditions

这里 的skip 条件是，

if i != 0 and nums[i] == nums[i-1] and (cur == [] or i-1 not in usedIndex)

因为 我们只考虑所有重复 数字的第一次出现，才会进入 下一步recursion，

比如 [1,1,2]

如果 1 之前出现过，而没有被用上，就表示 我们 已经考虑过 以1 为主的permutation了，如果被用上了，就表示 这次还是 第一次permute 该 数字。

class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        res = []
        usedIndex = []
        self.dfsVisit(nums, res, usedIndex, [])

        return res

    def dfsVisit(self, nums, res, usedIndex, cur):
        if len(cur) == len(nums):
            res.append(cur[:])
            return
        for i in range(len(nums)):

            if i != 0 and nums[i] == nums[i-1] and (cur == [] or i-1 not in usedIndex):
                continue
            if i not in usedIndex:
                self.dfsVisit(nums, res, usedIndex + [i], cur + [nums[i]])