LeetCode Combination Sum：組合總和

題目描述

給定無重複正整數陣列 candidates 與目標值 target，找出所有和為 target 的組合。candidates 中數字可無限重複使用。組合內非遞減，結果無重複組合。

例：candidates = [2,3,6,7], target = 7 → [[7], [2,2,3]]。

解法：回溯 + 剪枝

1. 排序 candidates。
2. 遞歸函數 dfs(index, target, path)：從 index 開始嘗試每個數，若 target < candidates[i] 剪枝；選擇該數加入 path，遞歸 dfs(i, target - candidates[i], path)（注意傳 i 允許重複使用）；回溯移除。
3. target == 0 找到一組解。

C# 實現

public IList<IList<int>> CombinationSum(int[] candidates, int target) {
    if (candidates == null || candidates.Length == 0) return null;
    var arr = candidates.OrderBy(x => x).ToList();
    var result = new List<IList<int>>();
    Travel(arr, new List<int>(), 0, target, result);
    return result;
}
private void Travel(IList<int> candidates, IList<int> path, int index, int target, IList<IList<int>> result) {
    if (target == 0) { result.Add(new List<int>(path)); return; }
    for (int i = index; i < candidates.Count; ++i) {
        if (target < candidates[i]) return;
        path.Add(candidates[i]);
        Travel(candidates, path, i, target - candidates[i], result);
        path.RemoveAt(path.Count - 1);
    }
}

關鍵點

• 排序 + 從 index 開始保證組合非遞減、無重複。
• 傳 i 而非 i+1 允許重複使用同一數字。
• target < candidates[i] 利用有序性剪枝。