LeetCode: 46. Permutations

DFS Solution.

from itertools import permutations

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        # Using Library
        # return list(permutations(nums, len(nums)))
        ret = []
        self.helper(nums, [], ret)
        return ret
        
    def helper(self, nums, element, ret):
        if not nums:
            ret.append(element)
        for i, num in enumerate(nums):
            self.helper(nums[:i]+nums[i+1:], element+[num], ret)

A lazy solution using generator.

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        self.ret = []
        for out in self.gen(nums):
            self.ret.append(out)
        return self.ret
        
    def gen(self, nums):
        if not nums:
            yield []
        
        for i, num in enumerate(nums):
            for out in self.gen(nums[:i]+nums[i+1:]):
                yield [num] + out