Full Permutation (Python)

LeetCode link

to flash back Time complexity O(n * n!)

Time complexity analysis ：

1. First time from n Number selected Second times from n - 1 Choose a few … Total choices n！
2. At the end of recursion Copy array time complexity O(n)
3. comprehensive 1 2 The sum O(n * n!)

Move the selected number to the left each time Next time select... From the numbers on the right

class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
''' hold nums The array is divided into left and right sides Maintain a boundary index Every time Move the selected element from the remaining elements to the left '''
n = len(nums)
res_list = []
def doit(first):
if first == n:
res_list.append(nums[:])
# Each layer selects one of the remaining elements on the right 
for i in range(first, n):
# The selected elements are added to the left 
nums[i], nums[first] = nums[first], nums[i]
# Boundary index +1 Go to the next floor 
doit(first + 1)
# after Remember to swap the elements back Start the next cycle 
nums[i], nums[first] = nums[first], nums[i]
doit(0)
return res_list

Use an array of tags of the same size to indicate whether you have previously selected

class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res_list = []
path = []
nums_len = len(nums)
# An array of tags of the same size To mark whether a subscript has been selected 
selected = [False for _ in range(nums_len)]
def doit():
if len(path) == nums_len:
res_list.append(path[:])
return
for i in range(nums_len):
if not selected[i]:
# Mark selected 
selected[i] = True
# add value 
path.append(nums[i])
doit()
# Roll back 
path.pop()
selected[i] = False
doit()
return res_list