Python easy to understand backtracking solution.


  • 0
    C
    # 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

  • 5
    C

    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)

  • 0

    @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!


  • 0
    N

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


Log in to reply
 

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