回溯法經典練習：組合總和的深度解析與實戰
引言
在算法世界里，回溯法（Backtracking）是解決 組合、排列、子集 等問題的神器。而 “組合總和”（Combination Sum） 問題，更是回溯算法中的經典代表，幾乎是算法面試中的常客。
今天，我就帶大家從 直覺理解 到 代碼實戰，深入解析回溯法如何求解 組合總和，并給出代碼詳解，帶你徹底吃透這個問題！
1. 題目解析
🔹 題目描述
給定一個 無重復元素 的正整數數組 candidates，以及一個目標值 target，找到所有可以使數字和為 target 的 唯一組合。
要求：
- 同一個數字可以被無限次使用，但組合的順序不影響結果（即
{2,2,3}和{3,2,2}視為相同組合）。 - 結果集不能包含重復的組合。
示例：
輸入: candidates = [2,3,6,7], target = 7
輸出: [[2,2,3],[7]]
解釋: 2+2+3 = 7, 7 = 7，因此答案是 [[2,2,3],[7]]
2. 直覺思考
這個問題的求解方式，可以類比 爬樓梯：
- 每次選擇一個數（例如 2 或 3 或 6 或 7）。
- 判斷當前累加和是否等于目標值 target。
- 如果超過 target，則不合法，剪枝回溯。
- 如果剛好等于 target，就加入結果集。
看到 “所有組合”、“無序”、“可以重復選擇” 這些關鍵詞，回溯法就是最佳選擇！
3. 回溯算法核心框架
回溯法的核心思路是 “遞歸 + 回溯 + 剪枝”，通常分為以下幾個步驟：
- 終止條件：當當前路徑的總和等于
target，將其加入結果集。 - 選擇操作：從
candidates里選擇一個數，嘗試加入當前路徑。 - 遞歸調用：累加該數后，繼續探索下一個可能的組合。
- 回溯撤銷選擇：探索完該路徑后，撤銷最后一個選擇，回溯到上一步繼續嘗試其他數。
回溯法的框架：
def backtrack(路徑, 選擇列表):if 滿足結束條件:記錄結果returnfor 選擇 in 選擇列表:做選擇backtrack(路徑, 選擇列表) # 遞歸撤銷選擇 # 回溯
4. 代碼實戰
🔹 Python 代碼
from typing import Listdef combinationSum(candidates: List[int], target: int) -> List[List[int]]:res = [] # 結果集def backtrack(start, path, total):# 遞歸終止條件：找到一個滿足條件的組合if total == target:res.append(path[:]) # 注意要拷貝 pathreturn# 遍歷候選數組for i in range(start, len(candidates)):num = candidates[i]# 剪枝：如果 total + num 超過 target，則不再繼續if total + num > target:continue# 選擇當前數字，遞歸path.append(num)backtrack(i, path, total + num) # 這里 `i` 而不是 `i+1`，因為允許重復選擇path.pop() # 回溯，撤銷選擇# 從索引 0 開始搜索backtrack(0, [], 0)return res
5. 代碼詳解
🔸 遞歸邏輯
backtrack(start, path, total)start：控制遞歸深度，避免重復選擇前面的數。path：記錄當前的組合路徑。total：當前路徑的累加和。
🔸 關鍵點
- 循環遍歷
candidates：- 從
start位置開始，避免重復使用已選過的數。 - 允許重復選擇
candidates[i]，所以backtrack(i, ...)而不是backtrack(i+1, ...)。
- 從
- 剪枝優化：
- 當
total + num > target時，提前終止遞歸，避免不必要的計算。
- 當
- 回溯撤銷選擇：
- 遞歸完一個分支后，撤銷
path.append(num)的選擇，繼續嘗試其他數。
- 遞歸完一個分支后，撤銷
6. 測試代碼
candidates = [2, 3, 6, 7]
target = 7
print(combinationSum(candidates, target))
輸出結果：
[[2, 2, 3], [7]]
7. 復雜度分析
假設 candidates 長度為 N，目標值 target：
- 最壞情況下，回溯的搜索樹是一個
N叉樹，高度為target/min(candidates)。 - 時間復雜度 近似為
O(2^N)（指數級）。 - 空間復雜度 近似
O(N)（遞歸棧空間 + 結果集存儲）。
8. 進階優化
🔹 剪枝優化
在搜索前 先對 candidates 排序，一旦發現 total + num > target，就可以提前停止當前分支，減少不必要的遞歸：
candidates.sort() # 先排序，提高剪枝效率
🔹 記憶化搜索
如果 candidates 很多，可以用 字典（哈希表） 存儲 target 計算結果，避免重復計算。
9. 結語
回溯法是組合問題的利器，而 “組合總和” 這個問題，是典型的 遞歸 + 剪枝 題目，掌握它，你就能輕松應對類似的算法題。
🔹 復習總結
- 回溯三步走：選擇 -> 遞歸 -> 回溯。
- 通過
start參數避免重復，i位置不變以允許重復選取數字。 - 剪枝優化：如果
total + num > target，則立即跳過。 - 理解遞歸樹的結構，有助于更好地 Debug。
