題目描述
給定一個可能包含重複數字的整數數組 candidates 和一個目標值 target，找出所有的唯一組合，使得這些組合中的數字和為 target。
範例 1
輸入: candidates = [10,1,2,7,6,1,5], target = 8
輸出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
範例 2
輸入: candidates = [2,5,2,1,2], target = 5
輸出:
[
[1,2,2],
[5]
]
條件限制
- 所有的數字都是正整數。
- 答案中的每個組合都是唯一的。
- 答案中的組合可以按任意順序返回。
解題思路
這是一個典型的回溯法（Backtracking）問題，但與 39. Combination Sum 不同的是，這裡的數組中可能包含重複元素，我們需要特別處理去重問題。
核心點：
- 數組中可能有重複元素，我們需要避免出現重複的組合。
- 將數組排序後，對於相同元素，只允許第一次進入回溯，後續跳過。
- 每個數字只能使用一次，這與 39. Combination Sum 中數字可重複選取的要求不同。
解法一：回溯法
思路
- 排序：對數組進行排序，有助於處理重複元素的問題。
- 剪枝：在遞迴中，當
target小於 0 時，停止遞迴。 - 跳過重複元素：在同一層遞迴中，如果數字和前一個數字相同，則跳過，避免重複組合。
程式碼
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
def backtrack(start, target, path):
if target == 0:
result.append(list(path)) # 找到一個組合
return
if target < 0:
return # 剪枝
for i in range(start, len(candidates)):
# 跳過同層中重複的數字
if i > start and candidates[i] == candidates[i - 1]:
continue
path.append(candidates[i]) # 選擇當前數字
backtrack(i + 1, target - candidates[i], path) # 遞迴進入下一層
path.pop() # 撤銷選擇
candidates.sort() # 排序
result = []
backtrack(0, target, [])
return result
時間與空間複雜度分析
- 時間複雜度：O(2^n)，
n為候選數組的長度。最壞情況下，我們需要探索所有可能的組合。 - 空間複雜度：O(n)，
n是遞迴深度（對應目標值target）。
解法二：動態規劃
雖然回溯法已經是該問題的主流解法，但我們可以嘗試用動態規劃解決。
思路
- 排序：與回溯法類似，排序能幫助處理重複數字的問題。
- 狀態定義：
- 使用 dp[i] 表示所有和為 i 的組合。
- 轉移方程：
- 當考慮某個數字 num 時，對於所有和 j，將 dp[j - num] 的組合加上 num，形成新的組合，加入 dp[j]。
- 去重：
- 過程中需檢查是否有重複的組合。
程式碼
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
dp = [set() for _ in range(target + 1)]
dp[0].add(()) # 和為 0 的組合為空元組
for num in candidates:
for j in range(target, num - 1, -1):
for comb in dp[j - num]:
dp[j].add(comb + (num,))
return [list(comb) for comb in dp[target]]
時間與空間複雜度分析
- 時間複雜度：O(n * target)，其中
n是候選數組的長度，target是目標值。 - 空間複雜度：O(target)，需要儲存
dp陣列。
結論
- 回溯法 是解決該問題的經典方法，適合大多數情況。
- 動態規劃 雖然可以處理該問題，但實際使用中較少，適合性能要求較高的場合。
- 若候選數組較小，建議使用回溯法；若目標值較大，可以考慮動態規劃。
