LeetCode 筆記 - 77. Combinations

題目在此 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

相關文章