Python DFS solution 80ms


  • 0
    G

    A bit slow, but here is my solution using DFS:

    def permute(nums):
        stack = [([])]
        res = []
        
        while stack:
            comb = stack.pop()
            if len(comb) == len(nums):
                res.append(comb)
                continue
            for n in range(0, len(nums)):
                if nums[n] not in comb:
                    stack.append((comb + [nums[n]]))
        return res
    

    Any idea how to improve? Or should I avoid DFS for generating permutation?


  • 0
    G

    Still faster than this one though:

    class Solution(object):
        def next(self, nums):
            i = j = l = len(nums)-1
            while i>0 and nums[i] <= nums[i-1]:
                i -= 1
            if i>0:
                while nums[j] <= nums[i-1]:
                    j -= 1
                nums[j], nums[i-1] = nums[i-1], nums[j]
            while i<l:
                nums[i], nums[l] = nums[l], nums[i]
                i += 1
                l -= 1
                    
        def permute(self, nums):
            res = []
            res.append(list(nums))
            self.next(nums)
            
            while nums not in res:
                res.append(list(nums))
                self.next(nums)
            return res

  • 0
    C

    It will not work when you have repeated items in the list.


Log in to reply
 

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