本文為Python算法題集之一的代碼示例

題39：組合總和

1. 示例說明

• 給你一個 無重復元素 的整數數組 candidates 和一個目標整數 target ，找出 candidates 中可以使數字和為目標數 target 的 所有 不同組合 ，并以列表形式返回。你可以按 任意順序 返回這些組合。

  candidates 中的 同一個 數字可以 無限制重復被選取 。如果至少一個數字的被選數量不同，則兩種組合是不同的。

  對于給定的輸入，保證和為 target 的不同組合數少于 150 個。

  示例 1：

  輸入：candidates = [2,3,6,7], target = 7
  輸出：[[2,2,3],[7]]
  解釋：
  2 和 3 可以形成一組候選，2 + 2 + 3 = 7 。注意 2 可以使用多次。
  7 也是一個候選， 7 = 7 。
  僅有這兩種組合。
  

  示例 2：

  輸入: candidates = [2,3,5], target = 8
  輸出: [[2,2,2,2],[2,3,3],[3,5]]
  

  示例 3：

  輸入: candidates = [2], target = 1
  輸出: []
  

  提示：

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • candidates 的所有元素 互不相同
  • 1 <= target <= 40

---

2. 題目解析

- 題意分解

1. 本題是計算多個集合之間的求和問題，每個集合由若干個同樣的整數組成
2. 同樣整數和不能超過target，所以多個集合都是有限集合，因此每個集合能合成出來的數值也是有限的，可以用回溯法求解
3. 回溯法（探索與回溯法）是一種選優搜索法，又稱為試探法，按選優條件向前搜索，以達到目標。但當探索到某一步時，發現原先選擇并不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法。

- 優化思路

1. 通常優化：減少循環層次

2. 通常優化：增加分支，減少計算集

3. 通常優化：采用內置算法來提升計算速度

4. 分析題目特點，分析最優解

   1. 可以在回溯算法中使用值傳遞

   2. 可以在回溯算法中使用引用傳遞，但是應用傳遞必須解決回退操作，可以使用堆棧結構

   3. 可以考慮存儲過程值列表，最后將等于target的集合返回

---

- 測量工具

• 本地化測試說明：LeetCode網站測試運行時數據波動很大【可把頁面視為功能測試】，因此需要本地化測試解決數據波動問題
• CheckFuncPerf（本地化函數用時和內存占用測試模塊）已上傳到CSDN，地址：Python算法題集_檢測函數用時和內存占用的模塊
• 本題本地化超時測試用例自己生成，詳見章節【最優算法】，代碼文件包含在【相關資源】中

---

3. 代碼展開

1) 標準求解【值傳遞+回溯】

使用列表作為值傳遞參數，逐層遞歸，完成回溯

頁面功能測試，馬馬虎虎，超過40%

import CheckFuncPerf as cfpclass Solution:def combinationSum_base(self, candidates, target):def bracktracing(candidates, begin, ilen, path, ret, target):if target < 0:returnif target == 0:ret.append(path)returnfor iIdx in range(begin, ilen):bracktracing(candidates, iIdx, ilen, path + [candidates[iIdx]], ret, target - candidates[iIdx])ilen = len(candidates)path, result = [], []if ilen == 0:return resultbracktracing(candidates, 0, ilen, path, result, target)return resultaSolution = Solution()
result = cfp.getTimeMemoryStr(aSolution.combinationSum_base, nums, target)
print(result['msg'], '執行結果 = {}'.format(len(result['result'])))# 運行結果
函數 combinationSum_base 的運行時間為 1076.25 ms；內存使用量為 12060.00 KB 執行結果 = 62271

2) 改進版一【引用傳遞+堆棧回溯】

使用列表作為引用傳遞參數，逐層遞歸，完成回溯

頁面功能測試，馬馬虎虎，超越71%

import CheckFuncPerf as cfpclass Solution:def combinationSum_ext1(self, candidates, target):candidates.sort()path, result = [], []idx, isum = 0, 0def bracktracing(idx, isum, path):if sum(path) == target:result.append(path[:])returnfor jIdx in range(idx, len(candidates)):if isum + candidates[jIdx] > target:returnpath.append(candidates[jIdx])isum += candidates[jIdx]bracktracing(jIdx, isum, path)path.pop()isum -= candidates[jIdx]bracktracing(idx, isum, path)return resultaSolution = Solution()
result = cfp.getTimeMemoryStr(aSolution.combinationSum_base, nums, target)
print(result['msg'], '執行結果 = {}'.format(len(result['result'])))# 運行結果
函數 combinationSum_base 的運行時間為 1076.25 ms；內存使用量為 12060.00 KB 執行結果 = 62271

3) 改進版二【過程值列表緩存+遍歷后檢索】

使用多維列表結構保存各數值對應的組合列表，遍歷完成后下標檢索對應組合列表

頁面功能測試，馬馬虎虎，超過23%

import CheckFuncPerf as cfpclass Solution:def combinationSum_ext2(self, candidates, target):import copycandidates.sort()dp = [[] for x in range(target + 1)]for candidate in candidates:for iIdx in range(candidate, target + 1):if candidate == iIdx:dp[iIdx].append([candidate])else:for combination in dp[iIdx - candidate]:tmpgroup = copy.deepcopy(combination)tmpgroup.append(candidate)dp[iIdx].append(tmpgroup)return dp[target]aSolution = Solution()
result = cfp.getTimeMemoryStr(aSolution.combinationSum_base, nums, target)
print(result['msg'], '執行結果 = {}'.format(len(result['result'])))# 運行結果
函數 combinationSum_base 的運行時間為 1076.25 ms；內存使用量為 12060.00 KB 執行結果 = 62271

---

4. 最優算法

根據本地日志分析，最優算法為第1種方式【值傳遞+回溯】combinationSum_base

本題測試數據，似乎能推出以下結論：

1. 組合的回溯求解中，值傳遞性能優于引用傳遞的堆棧結構
2. 內存對象過多后，性能下降明顯，如combinationSum_ext2

nums = [x for x in range(10, 20)]
target = 200
aSolution = Solution()
result = cfp.getTimeMemoryStr(aSolution.combinationSum_base, nums, target)
print(result['msg'], '執行結果 = {}'.format(len(result['result'])))
result = cfp.getTimeMemoryStr(aSolution.combinationSum_ext1, nums, target)
print(result['msg'], '執行結果 = {}'.format(len(result['result'])))
result = cfp.getTimeMemoryStr(aSolution.combinationSum_ext2, nums, target)
print(result['msg'], '執行結果 = {}'.format(len(result['result'])))# 算法本地速度實測比較
函數 combinationSum_base 的運行時間為 1076.25 ms；內存使用量為 12060.00 KB 執行結果 = 62271
函數 combinationSum_ext1 的運行時間為 1243.29 ms；內存使用量為 11848.00 KB 執行結果 = 62271
函數 combinationSum_ext2 的運行時間為 14627.27 ms；內存使用量為 16080.00 KB 執行結果 = 62271

---

5. 相關資源

本文代碼已上傳到CSDN，地址：Python算法題源代碼_LeetCode(力扣)_組合總和

一日練，一日功，一日不練十日空

may the odds be ever in your favor ~