LeetCode 筆記 - 77. Combinations

Posted on Edited on

題目在此 77. Combinations

給兩個正整數 n, k，計算出 1 ~ n 所有長度為 k 的排列組合

解題思維

這題直覺可以用 Depth First Search
但發現只會落在第二座山裡

後來發現可以用 Divide and conquer
可以達到更有效率的組合

程式碼

Depth First Search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    
    def dfs(self, n_list, n, k, index, level, result):
        if level == k:
            self.result.append(result.copy())
            return
        for i in range(index, n):
            self.dfs(n_list, n, k, i + 1, level + 1, result + [n_list[i]])
        
    def combine(self, n: int, k: int) -> List[List[int]]:
        
        self.result = []
        
        n_list = [i for i in range(1, n + 1)]
        
        self.dfs(n_list, n, k, 0, 0, [])
        
        return self.result

Divide and conquer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def com(n: int, k: int) -> List[List[int]]:
            if k == 1:
                result = [[i] for i in range(1, n + 1)]
                return result
            else:
                result = []

                last_layer_result = self.combine(n - 1, k - 1)
                for i in last_layer_result:
                    # [1] [2] [3] in 4, 2
                    for j in range(i[-1] + 1, n + 1):
                        # [1, 2] [2, 3] [3, 4] in 4, 2
                        result.append(i + [j])

                return result

        result = com(n, k)

        return result