LeetCode 筆記 - 77. Combinations
針對組合生成問題，本文比較了深度優先搜尋（DFS）與分治法（Divide and Conquer）的效能差異。最終採用分治法策略，透過逐步組合子規模的結果，達成比傳統遞迴更高效的組合生成，優化了大範圍數據下的執行效率。
題目在此 77. Combinations
給兩個正整數 n, k，計算出 1 ~ n 所有長度為 k 的排列組合
解題思維
這題直覺可以用 Depth First Search
但發現只會落在第二座山裡
後來發現可以用 Divide and conquer
可以達到更有效率的組合
當 k 為 1 時，我們可以直接回傳 [[i] for i in range(1, n + 1)]。
當 k 大於 1 時，我們可以先找出 n - 1 裡面所有長度為 k - 1 的組合，再把後面缺少的候選加進去。
程式碼
Depth First Search1
2
3
4
5
6
7
8
9
10
11
12
13
14class 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 conquer1
2
3
4
5
6
7
8
9
10
11
12
13class 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