題目解釋
給定一組 distinct 的 candidates
整數和一個目標整數 target
,
傳回 candidates
的所有的唯一組合,且其中所選數字總和等於 target
。
您可以 以任何順序回傳組合。
可以從 candidates
中無限次地選擇相同的號碼。兩個組合是唯一的。
範例
- 輸入:
candidates = [2, 3, 6, 7], target = 7
- 輸出:
[[2, 2, 3],[7]]
2
和 3
是 candidate,因為 2 + 2 + 3 = 7
。
7
也是 candidate,因為 7 = 7
。 這是僅有的兩種組合。
最佳解法
(建議) 前導題目:【Leetcode 筆記】78. Subsets
經典的排列組合題,這邊借用 Neetcode 畫的圖,原始解說連結 點此。
可以發現是換湯不換藥的進階版 【Leetcode 筆記】78. Subsets
。
深入 trace
不過這次 subsets
的組合要丟進 results
裡面前,
要先判定一下 target - candidates[i]
是不是 >= 0
,
如果相減之後甚至變成負數,就代表可以直接跳過那個組合了,
因為他們不可能組成一個有效的 combination。
而這題因為同一個數字可以放在 combination 內複數次,
所以我們用迴圈去做遞迴會比較好,
可以將同一個位置的元素拆成兩種控制項: start
跟 i
進去,
另外要注意的點是迴圈的起始點會隨著 start
變動。
迴圈呼叫的順序
candidates = [2, 3, 6, 7], target = 7
i, target - candidates[i]
(0, 7 - 2 ) => 5
(1, 5 - 2 ) => 3
(2, 3 - 3 ) => 0
target == 0,開始向上 return !
...
程式碼
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
results = []
combinations = []
def _dfs(start, target):
if target == 0:
results.append(combinations.copy())
return
elif target < 0:
return
else:
for i in range(start, len(candidates)):
combinations.append(candidates[i])
_dfs(i, target - candidates[i])
combinations.pop()
_dfs(0, target)
return results
時間複雜度
O(n * 2^n)
,n 是 candidates
的長度。
2^n
是 combinations
的總數,對於每個 combinations,
我們可能需要 O(n)
的時間來複製並把它加到結果集中。
空間複雜度
O(n)
,n 是 candidates
的長度。
結語
高頻題,務必好好把握❗
- [推薦工具] 讓程式碼截圖變的美美的吧!VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
- [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
- [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26