Promble

link: https://leetcode.com/problems/permutations/

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Input: nums = [1]
Output: [[1]]

Approach 1

use itertools libs.

Thought

1. return list(permutations(nums)) 📓 permutations need to use list to return.

Code

from itertools import permutations

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]: 
         return list(permutations(nums))

Approach 2

back track

Thought

1. def ans:list to store the final result.
2. def backtrack, var curr:list is ans.
   1. first the ans is []
   2. judge if len(curr) == len(nums): ans.append(curr[:]) return
   3. loop num in nums:
      1. if num not in curr: curr.append(num)
      2. recurrence backtrack
      3. curr.pop()
3. the final result is ans.

Code

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 

Approach 3

dfs method.

Thought

1. permutations:list store the final result.
2. into self.dfs(nums, permutation, visited, permutations)
3. return the permutations

dfs:

1. def dfs(nums, permutations, visited, permutations) nums is the list, permutations is the list to temp store the num in nums, visited to store the visited num, permutations is the final result.
2. first judge if len(nums) == len(permutations): permutations.append(llist(permutation)), return # change the state
3. loop num in nums
   1. judge if num in visited: continue;
   2. add num into permutation
   3. add num into visited, because it also visited
   4. recurrence the self.dfs function.
   5. remove the num from visited.
   6. pop last num from permutation.

Code

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        if not nums:
            return [[]]

        permutations = []
        self.dfs(nums, [], set(), permutations)
        return permutations 

    def dfs(self, nums, permutation, visited, permutations):
        if len(nums) == len(permutation):
            permutations.append(list(permutation))
            return 

        for num in nums:
            if num in visited:
                continue;
            permutation.append(num)
            visited.add(num)
            self.dfs(nums, permutation, visited, permutations)
            visited.remove(num)
            permutation.pop()