# DFS
def permuteUnique(self, nums):
res, visited = [], [False]*len(nums)
nums.sort()
self.dfs(nums, visited, [], res)
return res
def dfs(self, nums, visited, path, res):
if len(nums) == len(path):
res.append(path)
return
for i in xrange(len(nums)):
if not visited[i]:
if i>0 and not visited[i1] and nums[i] == nums[i1]: # here should pay attention
continue
visited[i] = True
self.dfs(nums, visited, path+[nums[i]], res)
visited[i] = False
Python easy to understand backtracking solution.


After some thoughts about this backtracking solution, I found the visited flag is not needed. Here is an updated version:
def permuteUnique(self, nums): res = [] nums.sort() self.dfs(nums, [], res) return res def dfs(self, nums, path, res): if not nums: res.append(path) for i in xrange(len(nums)): if i > 0 and nums[i] == nums[i1]: continue self.dfs(nums[:i]+nums[i+1:], path+[nums[i]], res)

@caikehe Hi Your first solution is pretty straight forward, but how to derive the second solution?
Why visited flag not needed anymore? Could you give me some more hint?Thanks!

amazing solution! @coder42 I wondered the same thing  I think it is due to the sorting of nums!