46 Permutations

Permutations - LeetCode

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

  • c0
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        return list(itertools.permutations(nums, len(nums)))
  • code
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        def backTracking(nums, path, res):
            if not nums:
                res.append(path)
            for i in range(len(nums)):
                backTracking(nums[:i] + nums[i+1:], path + [nums[i]], res)
        backTracking(nums, [], res)
        return res

dfs(nums = [1, 2, 3] , path = [] , result = [] ) |____ dfs(nums = [2, 3] , path = [1] , result = [] ) | |___dfs(nums = [3] , path = [1, 2] , result = [] ) | | |___dfs(nums = [] , path = [1, 2, 3] , result = [[1, 2, 3]] ) # added a new permutation to the result | |___dfs(nums = [2] , path = [1, 3] , result = [[1, 2, 3]] ) | |___dfs(nums = [] , path = [1, 3, 2] , result = [[1, 2, 3], [1, 3, 2]] ) # added a new permutation to the result |____ dfs(nums = [1, 3] , path = [2] , result = [[1, 2, 3], [1, 3, 2]] ) | |___dfs(nums = [3] , path = [2, 1] , result = [[1, 2, 3], [1, 3, 2]] ) | | |___dfs(nums = [] , path = [2, 1, 3] , result = [[1, 2, 3], [1, 3, 2], [2, 1, 3]] ) # added a new permutation to the result | |___dfs(nums = [1] , path = [2, 3] , result = [[1, 2, 3], [1, 3, 2], [2, 1, 3]] ) | |___dfs(nums = [] , path = [2, 3, 1] , result = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]] ) # added a new permutation to the result |____ dfs(nums = [1, 2] , path = [3] , result = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]] ) |___dfs(nums = [2] , path = [3, 1] , result = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]] ) | |___dfs(nums = [] , path = [3, 1, 2] , result = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]] ) # added a new permutation to the result |___dfs(nums = [1] , path = [3, 2] , result = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]] ) |___dfs(nums = [] , path = [3, 2, 1] , result = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] ) # added a new permutation to the result