【Leetcode 筆記】39. Combination Sum

題目解釋

給定一組 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 的長度。

結語

高頻題，務必好好把握❗

• About
• Latest Posts

數據女巫 𝔻.𝕡𝕪𝕤 🔮

𝐀𝐈 𝐀𝐫𝐭𝐢𝐬𝐭 • 𝐒𝐨𝐟𝐭𝐰𝐚𝐫𝐞 𝐄𝐧𝐠𝐢𝐧𝐞𝐞𝐫
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art

Latest posts by 數據女巫 𝔻.𝕡𝕪𝕤 🔮 (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