LeetCode 筆記 - 46. Permutations

題目在此 46. Permutations

給定一個不重複數列,計算出所有排列

解題思維

這是全排列的經典題
可以使用 Depth First Search 或者使用交換陣列數值的方式達到效果

附上兩種程式碼

Depth First Search time complexity: O(V + E)
複雜度分析

SWAP time complexity: O(n!)
複雜度分析

程式碼

Depth First Search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class 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
image 106

SWAP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class 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

也許你也會想看看