題目描述
給定一個無重複正整數數組 candidates 和一個目標值 target，找出所有可以使數字和為 target 的組合。
數組中的數字可以無限制重複選取，並且所有的組合需要是唯一的。
範例 1
輸入: candidates = [2,3,6,7], target = 7
輸出: [[2,2,3],[7]]
解釋:
2 + 2 + 3 = 7
7 = 7
範例 2
輸入: candidates = [2,3,5], target = 8
輸出: [[2,2,2,2],[2,3,3],[3,5]]
範例 3
輸入: candidates = [2], target = 1
輸出: []
條件限制
- 所有數字（包括
target）均為正整數。 - 數組中所有數字互不相同。
- 答案中的組合可以按任意順序返回。
解題思路
這是一個經典的「組合問題」，解題的核心是利用回溯法（Backtracking）。
回溯法的思路
- 將候選數組進行排序（有助於提前剪枝）。
- 使用遞迴探索所有可能的組合。
- 當當前組合的總和等於目標時，將組合加入答案。
- 如果總和超過目標值，則停止探索（剪枝）。
解法一：回溯法
思路
- 從候選數組中依次選取元素。
- 選取後，繼續探索包含該元素的子問題。
- 如果總和超過
target，停止探索（剪枝）。 - 當總和等於
target，將當前組合加入結果集。
程式碼
class Solution:
def combinationSum(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)):
path.append(candidates[i]) # 選擇當前元素
backtrack(i, target - candidates[i], path) # 繼續探索
path.pop() # 撤銷選擇
result = []
candidates.sort() # 排序有助於剪枝
backtrack(0, target, [])
return result
時間與空間複雜度分析
- 時間複雜度：O(2^t)，
t是目標值target，因為每個數字可能被多次選取並組成不同的組合。 - 空間複雜度：O(t)，遞迴的最大深度為
target。
解法二：動態規劃
思路
- 將問題轉化為背包問題（完全背包）。
- 定義
dp[i]為目標和為i的所有組合。 - 對於每個數字
num和目標值j，若j >= num，則將dp[j - num]中的組合加上num，形成新的組合，並存入dp[j]。
程式碼
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
dp = [[] for _ in range(target + 1)]
dp[0] = [[]] # 和為 0 時的組合為空組合
for num in candidates:
for j in range(num, target + 1):
for comb in dp[j - num]:
dp[j].append(comb + [num])
return dp[target]
時間與空間複雜度分析
- 時間複雜度：O(n * target)，其中
n是候選數組的大小，target是目標值。 - 空間複雜度：O(target)，因為需要儲存每個和的組合。
結論
- 回溯法 是解決這類組合問題的直觀方法，適合初學者。
- 動態規劃 適合對性能要求較高的情況，但編碼複雜度較高。
- 根據具體問題的規模選擇合適的解法：當
candidates較小時，使用回溯法；當目標值較大時，考慮動態規劃。
