LeetCode Combination Sum：回溯法求目標和組合（可重複選取）

題目大意

給定無重複正整數數組 candidates 和目標 target，找出所有**和為 target** 的組合。每個數字可**無限次**使用。解集不含重複組合。

回溯框架

1. 先排序 candidates，便於剪枝與去重。
2. 遞歸函數 dfs(start, target, path)：
    - target==0 → 記錄答案。
    - target<0 → 剪枝返回。
    - 從 start 到末尾遍歷：
     跳過重複元素（i>start && c[i]==c[i-1]）。
     選 c[i]，遞歸 dfs(i, target-c[i], path)（注意傳 i 而非 i+1，允許重複使用）。
     回溯彈出。

Java 實現

public List> combinationSum(int[] candidates, int target) {
    List> res = new ArrayList<>();
    Arrays.sort(candidates);
    backtrack(candidates, 0, target, new ArrayList<>(), res);
    return res;
}
void backtrack(int[] c, int start, int target, List path, List> res){
    if(target<0) return;
    if(target==0){ res.add(new ArrayList<>(path)); return; }
    for(int i=start;istart && c[i]==c[i-1]) continue; // 去重
        path.add(c[i]);
        backtrack(c, i, target-c[i], path, res); // i 允許重複
        path.remove(path.size()-1);
    }
}

複雜度

• 時間：指數級（NP 問題），實際受 target 與數值大小限制。
• 空間：遞歸棧深度 ≤ target/min(candidates)。

變體：Combination Sum II

每個數字**只能用一次** → 遞歸傳 i+1，其餘邏輯相同。