題目

  • 題目連結
  • 目標函式 : combinationSum(candidates, target)
    • Input : candidates: List[int]、target: int
    • Output : List[List[int]]

解題概念

  • 題意 :
    • 給予一整數陣列 candidates 與一目標整數 target，需要回傳 candidates 所有獨立組合的陣列，其中選擇的數字總和為 target。(組合的順序無所謂)
    • candidates 中同一數字可以被挑選無限次。
    • 總和為 target 之獨立組合的數量 $\lt$ 150

我的寫法

  • 想法 : 我覺得可以使用 DFS
    • 使用 solve(sum, candidate) 的函式，sum 為當回合需要處理的總和，candidate 為當回合可以使用的數字陣列
    • 而其中在遞迴時會有三種 cases 需要去處理，下列說明以 solve(sum = 7, candidate = [7, 6, 3, 2])
      1. 不選 7 + solve(sum = 7, candidate = [6, 3, 2])
      2. 只選 7 一次 + solve(sum = 7 - 7, candidate = [6, 3, 2])
      3. 會選 7 多次 + solve(sum = 7 - 7, candidate = [7, 6, 3, 2])
    • 最後將得到 3 個 cases 的結果彙整起來，再回傳結果
  • 遇到之困難 :
    1. 不知道要怎麼彙整 3 個 cases 的結果
    2. 不知道要怎麼設定遞迴回傳的資料型態

解答 or 其他優秀寫法

  • 想法 :
    • 其實根本不需要討論 3 個 cases 的部分
    • 而 solve() 根本不用回傳資料，而是直接對同一 list 進行修改即可，這樣就能解決回傳資料型態的問題
    • solve() 使用參數如下 :
      1. target : 當回合需要處理的總和
      2. index : 目前指到 candidate 索引值
      3. path : 當前該狀況累積的路徑陣列
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    def combinationSum(self, candidates, target):
        
        res = []

        def solve(target, index, path):

            # 若 target < 0，代表當前路徑不行，直接結束此路徑
            if target < 0 : return

            # 若 target == 0，代表當前路徑成立
            if target == 0 :
                res.append(path) # res 加入此路徑
                return # 結束路徑
            
            # 若 target > 0
            for i in xrange(index, len(candidates)):

                # 針對 candidates[index:len(candidates)]，去個別計算此路徑加上該 candidate 後的結果
                solve(target - candidates[i], i, path + [candidates[i]])

        solve(target, 0, [])

        return res
  • 成效 :
    • Time Complexity : $O(n^2)$
    • Runtime: 91 ms (faster than 14.29%)
    • Memory Usage: 13.4 MB (more than 57.18%)