LeetCode 筆記 - 77. Combinations

Posted on

題目在此 77. Combinations

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

解題思維

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

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

當 k 為 1 時，我們可以直接回傳 [[i] for i in range(1, n + 1)]。
當 k 大於 1 時，我們可以先找出 n - 1 裡面所有長度為 k - 1 的組合，再把後面缺少的候選加進去。

image 34

程式碼

Depth First Search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = []
        def dfs(start, values, level):
            if level == k:
                result.append(values)
                return
            
            for next_n in range(start + 1, n + 1):
                dfs(next_n, values + [next_n], level + 1)

        dfs(0, [], 0)

        return result

Divide and conquer

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        if k == 1:
            return [[i] for i in range(1, n + 1)]

        small_result = self.combine(n - 1, k - 1)

        result = []
        for small_r in small_result:
            for current_n in range(small_r[-1] + 1, n + 1):
                result.append(small_r + [current_n])

        return result

也許你也會想看看