[LeetCode 解題攻略] 39. Combination Sum

題目描述

給定一個無重複正整數數組 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）。

回溯法的思路

1. 將候選數組進行排序（有助於提前剪枝）。
2. 使用遞迴探索所有可能的組合。
3. 當當前組合的總和等於目標時，將組合加入答案。
4. 如果總和超過目標值，則停止探索（剪枝）。

解法一：回溯法

思路

1. 從候選數組中依次選取元素。
2. 選取後，繼續探索包含該元素的子問題。
3. 如果總和超過 target，停止探索（剪枝）。
4. 當總和等於 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。

解法二：動態規劃

思路

1. 將問題轉化為背包問題（完全背包）。
2. 定義 dp[i] 為目標和為 i 的所有組合。
3. 對於每個數字 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)，因為需要儲存每個和的組合。

結論

1. 回溯法 是解決這類組合問題的直觀方法，適合初學者。
2. 動態規劃 適合對性能要求較高的情況，但編碼複雜度較高。
3. 根據具體問題的規模選擇合適的解法：當 candidates 較小時，使用回溯法；當目標值較大時，考慮動態規劃。