題目
#

leetcode 39 - Combination Sum (題目說明請點連結)

題目簡述
#

給一個不重複的正整數陣列 candidates，以及一個目標數字 target。
找出所有和為 target 的組合，每個數字可以被重複選取多次。

範例
#

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

解題思路
#

這題要求我們找出所有數組中數字的組合，使其和等於目標值。每個數字可以被無限次使用。我們可以使用回溯法來解決這個問題，通過遞迴地嘗試每個數字，並在超過目標值時進行剪枝。

解法
#

Backtracking

初始化結果列表 res，用於存儲所有符合條件的組合
定義遞迴函數 backtrack，用於生成組合
在遞迴函數中：
- 如果目標值小於 0，返回
- 如果目標值等於 0，將當前路徑加入結果列表
- 遍歷候選數字，遞迴嘗試每個數字，並在遞迴返回後撤銷選擇
返回結果列表 res

步驟
#

初始化：
- 創建結果列表 res
遞迴生成組合：
- 定義遞迴函數 backtrack
- 在遞迴函數中，檢查目標值，遞迴嘗試每個數字
返回結果：
- 返回 res

例子說明
#

candidates = [2,3,6,7], target = 7

步驟	當前路徑	剩餘目標	操作
初始化	[]	7	開始遞迴
選擇 2	[2]	5	遞迴嘗試
選擇 2	[2,2]	3	遞迴嘗試
選擇 2	[2,2,2]	1	遞迴嘗試
選擇 2	[2,2,2,2]	-1	超過目標，返回
選擇 3	[2,2,3]	0	找到組合，加入結果
選擇 6	[6]	1	遞迴嘗試
選擇 7	[7]	0	找到組合，加入結果

完整程式碼
#

java

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(candidates, target, 0, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(int[] candidates, int target, int start, List<Integer> path, List<List<Integer>> res) {
        if (target < 0) {
            return; // 超過目標值，剪枝
        }
        if (target == 0) {
            res.add(new ArrayList<>(path)); // 找到一組符合的組合
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            path.add(candidates[i]); // 選擇 candidates[i]
            backtrack(candidates, target - candidates[i], i, path, res); 
            path.remove(path.size() - 1); // 撤銷選擇
        }
    }
}