題目描述:給定一個候選數字陣列 candidates(可能包含重複元素)和一個目標值 target,找出所有能使數字總和等於 target 的組合。每個數字在每個組合中只能使用一次,且結果中不能包含重複的組合。
解題思路:本題是 Combination Sum(39)的變體,主要差別在於:
解法的核心仍是回溯(Backtracking),但需要加入去重邏輯。
去重的關鍵:先對 candidates 排序。在回溯的每一層(同一個遞迴深度),若當前元素與前一個元素相同(candidates[i] == candidates[i-1])且 i > start(即不是這一層的第一個選擇),則跳過,以避免產生重複組合。
這個條件的意義:同一層中,第一次選擇某個值是合法的;但若前面已經選過相同的值並回溯了,再次選擇相同的值會產生完全相同的子樹(重複組合),所以跳過。
遞迴時,下一層從 i + 1 開始(不是 i),確保每個元素只用一次。
時間複雜度:O(2^n · n) — 最壞情況下(所有元素各不相同),回溯樹有 2^n 個葉節點;每個葉節點複製組合需 O(n)。排序需 O(n log n),但被回溯的指數項主導。實際上由於剪枝(candidates[i] > remaining 即 break)和去重,效率遠優於最壞情況。
空間複雜度:O(n) — 遞迴呼叫堆疊的深度最大為 n(所有元素都選入組合),current 陣列也最多 n 個元素。不計輸出結果所用的空間。
1. Sort candidates in ascending order
2. Define backtrack(remaining, start, current):
a. If remaining == 0: add copy of current to result, return
b. For i from start to end of candidates:
- If i > start AND candidates[i] == candidates[i-1]: skip (avoid duplicates at same level)
- If candidates[i] > remaining: break (pruning, rest are larger)
- Append candidates[i] to current
- Recurse: backtrack(remaining - candidates[i], i + 1, current)
- Remove last element from current (backtrack)
3. Call backtrack(target, 0, [])
4. Return result雜湊集合去重 O(2^n · n):不對輸入排序,而是將每個組合排序後存入 set<vector<int>> 去重。雖然邏輯簡單,但額外的排序和集合查詢成本高,且無法做剪枝優化,效率明顯較差。
動態規劃(DP)O(n · target):類似零錢兌換問題,用 DP 表記錄所有達到各子目標的組合。但此題需要列舉所有具體組合(而非只計數),DP 難以直接枚舉組合且去重邏輯複雜,回溯法在此更為自然。
if i > start && candidates[i] == candidates[i-1] 這個條件中,為何條件是 i > start 而不是 i > 0?改成 i > 0 會產生什麼問題?