題目出處
難度
medium
個人範例程式碼
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
if not n or not k:
return [[]]
elements = [i for i in range(1, n+1)]
ans = []
self.dfs(elements, k, [], ans)
return ans
def dfs(self, elements, k, combinations, ans):
# end of recursion
if k <= 0:
ans.append(combinations[:]) # deepcopy
return
if not elements:
return
# define and split
for i, element in enumerate(elements):
combinations.append(element)
self.dfs(elements[i+1:], k-1, combinations, ans)
combinations.pop() # backtracking
最近在練習程式碼本身就可以自解釋的 Coding style,可以嘗試直接閱讀程式碼理解
算法說明
本題是 Combinations 系列的第 1 題,其他的題目可以參考:
第 1 題:不允許重複,給定數字範圍的全部組合,目標是指定組合內固定的數量。
第 2 題:允許重複,順序不同視為相同結果,也就是說「(1,2,3) 與 (3, 2, 1) 是一個結果」
第 3 題:允許有限重複(題目指定上限數量),求全部組合。
第 4 題:不允許重複,給定數字範圍的全部組合,目標是求指定的和。
第 5 題:允許重複,但順序不同視為不同結果,也就是說「(1,2,3) 與 (3, 2, 1) 是兩個結果」。(這題已經可以當作排列的題目了。)
組合類的問題,使用 dfs 搜尋出全部的組合,
記得當 k = 4 時,實際上我們可用的數字是 「1,2,3,4」而非 「0,1,2,3」。
input handling
如果沒有 k 或 n,直接 return [[]]
Boundary conditions
用 dfs 來控制搜尋範圍,直到 「k <= 0」 或 「找不到新的元素」,return 結果
Reference
⭐ Leetcode 解題紀錄 ⭐ | 題型 | 資料結構 | Python Solution | C++ Solution | Note | |
---|---|---|---|---|---|---|
⭐BFS 相關題型 ⭐ | ||||||
104 | Maximum Depth of Binary Tree | BFS (分層) | Python | |||
94 | Binary Tree Inorder Traversal | BFS (分層) | Tree | Python | 內含 處理 Tree 樹問題的重點 | |
102 | Binary Tree Level Order Traversal | BFS (分層) | Tree | Python | ||
103 | Binary Tree Zigzag Level Order Traversal | BFS (分層) | Tree | Python | ||
107 | Binary Tree Level Order Traversal II | BFS (分層) | Tree | Python | ||
133 | Clone Graph | BFS (分層) | Graph | Python | Graph 的基本操作 #重要題型 | |
127 | Word Ladder | BFS (分層), DFS | Graph | Python | ||
[Lint] 127 | Topological Sorting | BFS (拓撲) | Python | 內有 indegree, outdegree 介紹 #重要題型 | ||
207 | Course Schedule | BFS (拓樸) | Graph | Python | ||
210 | Course Schedule II | BFS (拓樸) | Graph | Python | ||
[Lint] 892 | Alien Dictionary | BFS (拓樸) | Graph | Python | ||
[Lint] 431 | Connected Component in Undirected Graph | BFS (連通塊) | Graph | Python |