0%
Loading ...

【Leetcode 筆記】39. Combination Sum

image 1723995260868

題目解釋

給定一組 distinctcandidates 整數和一個目標整數 target
傳回 candidates 的所有的唯一組合,且其中所選數字總和等於 target
您可以 以任何順序回傳組合

可以從 candidates 中無限次地選擇相同的號碼。兩個組合是唯一的。

範例

  • 輸入: candidates = [2, 3, 6, 7], target = 7
  • 輸出: [[2, 2, 3],[7]]

23 是 candidate,因為 2 + 2 + 3 = 7
7 也是 candidate,因為 7 = 7。 這是僅有的兩種組合。

最佳解法

(建議) 前導題目:【Leetcode 筆記】78. Subsets

經典的排列組合題,這邊借用 Neetcode 畫的圖,原始解說連結 點此

file

可以發現是換湯不換藥的進階版 【Leetcode 筆記】78. Subsets

深入 trace

不過這次 subsets 的組合要丟進 results 裡面前,
要先判定一下 target - candidates[i] 是不是 >= 0
如果相減之後甚至變成負數,就代表可以直接跳過那個組合了,
因為他們不可能組成一個有效的 combination。

而這題因為同一個數字可以放在 combination 內複數次,
所以我們用迴圈去做遞迴會比較好,
可以將同一個位置的元素拆成兩種控制項: starti 進去,
另外要注意的點是迴圈的起始點會隨著 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^ncombinations 的總數,對於每個 combinations,
我們可能需要 O(n) 的時間來複製並把它加到結果集中。

空間複雜度

O(n),n 是 candidates 的長度。

結語

高頻題,務必好好把握❗

數據女巫 𝔻.𝕡𝕪𝕤 🔮

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

The reCAPTCHA verification period has expired. Please reload the page.