46. Permutations

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/permutations
• topics: Backtracking

Given an array nums of distinct integers, return all the possible  permutations. You can return the answer in any order.# Simple recursion not very efficient

Simple Recursion

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ans = []
        def permute_step(prev, depth):
            depth -= 1
            if not depth:
                for t in nums:
                    if t not in prev:
                        ans.append(prev + [t])
            else:
                for t in nums:
                    if t not in prev:
                        permute_step(prev + [t], depth)
 
        permute_step([], len(nums))
        return ans
                 

Backtracking More Efficient

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def backtrack(curr):
            if len(curr) == len(nums):
                ans.append(curr[:])
                return
 
            for num in nums:
                if num not in curr:
                    curr.append(num)
                    backtrack(curr)
                    curr.pop()
 
        ans = []
        backtrack([])
        return ans

Itertools most efficient

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        return list(permutations(nums))