LeetCode 筆記 - 46. Permutations

Posted on Edited on

題目在此 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
23
24
25
class Solution:
    def dfs(self, data, data_length, visited, result):

        if data_length == len(visited):
            # print(result)
            self.result.append(result[:])
            return

        for i in range(data_length):
            if i in visited:
                continue

            self.dfs(data, data_length, visited + [i], result + [data[i]])

    def permute(self, nums: List[int]) -> List[List[int]]:

        l = len(nums)
        if l <= 1:
            return [nums]

        self.result = []

        self.dfs(nums, l, [], [])

        return self.result

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