A Python solution based on standard permutation - 130ms


  • 0
    G
    class Solution:
        # @param num, a list of integer
        # @return a list of lists of integers
        # 12:00
        def permuteUnique(self, num):
            output = []
            flags = [False] * len(num)
            
            self.permuteForReal(sorted(num), output, flags)
            
            return output
    
        def permuteForReal(self, num, output, flags, temp = None):
            temp = temp or []
            if len(temp) == len(num):
                output.append(temp[:])
                return
             
            for i in range(len(num)):
                if not flags[i]:
                    if i > 0 and not flags[i-1] and num[i] == num[i-1]:
                        continue
                    temp.append(num[i])
                    flags[i] = True
                    self.permuteForReal(num, output, flags, temp)
                    temp.pop()
                    flags[i] = False

  • 0
    C

    Nice idea, here is a revised version of your code:

    def permuteUnique(self, nums):
        res, flags = [], [False]*len(nums)
        nums.sort()
        self.dfs(nums, flags, [], res)
        return res
        
    def dfs(self, nums, flags, path, res):
        if len(nums) == len(path):
            res.append(path)
            return 
        for i in xrange(len(nums)):
            if not flags[i]:
                if i>0 and not flags[i-1] and nums[i] == nums[i-1]:
                    continue
                flags[i] = True
                self.dfs(nums, flags, path+[nums[i]], res)
                flags[i] = False

Log in to reply
 

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