Python DFS solution 80ms

  • 0

    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):
            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

    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 = []
            while nums not in res:
            return res

  • 0

    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.