題目描述:給定一個不含重複元素的正整數陣列 candidates 與目標值 target,找出所有加總等於 target 的組合。每個元素可以無限次重複使用,答案中不得有重複組合。
解題思路:使用回溯法,與子集問題的差異在於:同一個元素可以重複選取(遞迴時傳入相同的 start = i 而非 i+1),以及只有在路徑總和恰好等於 target 時才加入答案。為了剪枝(Pruning),可先對 candidates 排序,一旦當前元素已使剩餘目標變成負數,後面更大的元素必然也不合法,可直接 break 退出迴圈,大幅減少無效遞迴。
時間複雜度:O(n^(T/M)) — 其中 T 為 target,M 為 candidates 中的最小值。樹的最大深度為 T/M,每層最多 n 個分支,實際因剪枝而遠小於此上界。
空間複雜度:O(T/M) — 遞迴堆疊深度最多為 T/M(以最小元素填滿目標的步數),暫存路徑 path 的長度亦受此限制(不計輸出空間)。
1. Sort candidates in ascending order
2. Define backtrack(start, remaining, path):
a. If remaining == 0: append copy of path to result; return
b. For i from start to len(candidates)-1:
i. If candidates[i] > remaining: break (pruning)
ii. Push candidates[i] onto path
iii.Recurse: backtrack(i, remaining - candidates[i], path) (i not i+1: reuse allowed)
iv. Pop last element from path
3. Call backtrack(0, target, [])
4. Return result動態規劃 O(n · target):建立 dp[s] 表示加總為 s 的所有組合列表。從 s=1 枚舉到 target,對每個候選數更新 dp。適合只需計算組合數量而非枚舉所有組合的場景,但儲存所有組合時記憶體開銷極大。
BFS 層次遍歷:以初始狀態(剩餘 = target,路徑為空)為根,逐層擴展。最終層即為所有合法組合。與回溯法等價但使用佇列,通常不如回溯法節省空間。