LeetCode 筆記 - 46. Permutations
全排列問題的經典解析。本文介紹深度優先搜尋（DFS）與交換元素（SWAP）兩種主流解法，並針對兩者的時間複雜度進行深入對比。這是一篇幫助讀者掌握遞迴思維、理解排列組合生成邏輯以及演算法複雜度評估的技術指南。
題目在此 46. Permutations
給定一個不重複數列，計算出所有排列
解題思維
這是全排列的經典題
可以使用 Depth First Search 或者使用交換陣列數值的方式達到效果
附上兩種程式碼
Depth First Search time complexity: O(V + E)
複雜度分析
SWAP time complexity: O(n!)
複雜度分析
程式碼
Depth First Search1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
size = len(nums)
visited = set()
result = []
def dfs(values):
if len(values) == size:
result.append(values)
for i in range(size):
if i in visited:
continue
visited.add(i)
dfs(values + nums[i:i+1])
visited.remove(i)
dfs([])
return result
SWAP1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution:
def permutations(self, data, start_index, end_index):
if start_index == end_index:
if data not in self.result:
self.result.append(data[:])
return
for i in range(start_index, end_index):
data[i], data[start_index] = data[start_index], data[i]
self.permutations(data, start_index + 1, end_index)
data[i], data[start_index] = data[start_index], data[i]
def permute(self, nums: List[int]) -> List[List[int]]:
self.result = []
self.permutations(nums, 0, len(nums))
return self.result