題目解釋
給定一組 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 的長度。
結語
高頻題，務必好好把握
𝐀𝐈 𝐀𝐫𝐭𝐢𝐬𝐭 • 𝐒𝐨𝐟𝐭𝐰𝐚𝐫𝐞 𝐄𝐧𝐠𝐢𝐧𝐞𝐞𝐫
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art
Latest posts by 數據女巫 𝔻.𝕡𝕪𝕤 
(see all)
(see all)- [推薦工具] 讓程式碼截圖變的美美的吧！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
