[LeetCode解題攻略] 40. Combination Sum II

題目描述

給定一個可能包含重複數字的整數數組 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 不同的是，這裡的數組中可能包含重複元素，我們需要特別處理去重問題。

核心點：

1. 數組中可能有重複元素，我們需要避免出現重複的組合。
2. 將數組排序後，對於相同元素，只允許第一次進入回溯，後續跳過。
3. 每個數字只能使用一次，這與 39. Combination Sum 中數字可重複選取的要求不同。

解法一：回溯法

思路

1. 排序：對數組進行排序，有助於處理重複元素的問題。
2. 剪枝：在遞迴中，當 target 小於 0 時，停止遞迴。
3. 跳過重複元素：在同一層遞迴中，如果數字和前一個數字相同，則跳過，避免重複組合。

程式碼

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）。

解法二：動態規劃

雖然回溯法已經是該問題的主流解法，但我們可以嘗試用動態規劃解決。

思路

1. 排序：與回溯法類似，排序能幫助處理重複數字的問題。
2. 狀態定義：
3. • 使用 dp[i] 表示所有和為 i 的組合。
3. 轉移方程：
4. • 當考慮某個數字 num 時，對於所有和 j，將 dp[j - num] 的組合加上 num，形成新的組合，加入 dp[j]。
4. 去重：
5. • 過程中需檢查是否有重複的組合。

程式碼

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 陣列。

結論

1. 回溯法 是解決該問題的經典方法，適合大多數情況。
2. 動態規劃 雖然可以處理該問題，但實際使用中較少，適合性能要求較高的場合。
3. 若候選數組較小，建議使用回溯法；若目標值較大，可以考慮動態規劃。