# Python easy to understand backtracking solution.

• ``````# 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[i-1] and nums[i] == nums[i-1]:  # here should pay attention
continue
visited[i] = True
self.dfs(nums, visited, path+[nums[i]], res)
visited[i] = False``````

• 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[i-1]:
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!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.