全排列 （Python）

LeetCode鏈接

回溯 時間復雜度 O(n * n!)

時間復雜度分析：

1. 第一次從n個數中選 第二次從n - 1個數選… 總共的選擇 n！
2. 遞歸結束時 復制數組時間復雜度 O(n)
3. 綜合1 2 總復雜度 O(n * n!)

每次將選中的數字挪到左側 下一次在右側數字中選擇

class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
''' 把 nums數組分為左右兩邊 維護一個分界索引 每次把 從剩下的元素中選出的元素挪到左邊去 '''
n = len(nums)
res_list = []
def doit(first):
if first == n:
res_list.append(nums[:])
# 每一層都在右側剩余元素中選擇一個元素
for i in range(first, n):
# 選出的元素加入左側
nums[i], nums[first] = nums[first], nums[i]
# 分界索引+1 去下一層
doit(first + 1)
# 之後 記得把元素再交換回來 開啟下一輪循環
nums[i], nums[first] = nums[first], nums[i]
doit(0)
return res_list

使用相同大小的標記數組來表示之前是否選擇過

class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res_list = []
path = []
nums_len = len(nums)
# 一個相同大小的標記數組 來標記某個下標是否被選擇過
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]:
# 標記選過
selected[i] = True
# 添加值
path.append(nums[i])
doit()
# 回滾
path.pop()
selected[i] = False
doit()
return res_list