[Backtracking]47. Permutations I

• 分类：Backtracking
• 时间复杂度: O(n)

47. Permutations II

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

Example:

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

代码：

方法:

class Solution:
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res=[]
        
        if nums==None or len(nums)==0:
            return res
        list_=[]
        #加了这句用于去重
        nums.sort()
        visited=[False for i in range(len(nums))]
        self.helper(res,visited,list_,nums)
        return res
    
    def helper(self,res,visited,list_,nums):
        if len(list_)==len(nums):
            res.append(list_.copy())
        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
                
            list_.append(nums[i])
            visited[i]=True
            self.helper(res,visited,list_,nums)
            visited[i]=False
            list_.pop()

讨论：

和没有重复元素的 Permutation 一题相比，只加了两句话：

1. Arrays.sort(nums) // 排序这样所有重复的数
2. if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) { continue; } // 跳过会造成重复的情况，没行过就不要行了！