LeetCode 筆記 - 46. Permutations

Posted 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
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

相關文章