一、題目介紹
今天要練習的是 LeetCode 39：Combination Sum（組合總和）

題目給定一個由不同整數組成的陣列candidates，以及一個目標數字target，需要找出所有可以讓數字總和等於target的組合

其中有一個非常重要的條件：同一個數字可以被選擇多次

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

符合條件的組合為：
[
[2,2,3],
[7]
]

因為：
2 + 2 + 3 = 7
7 = 7

而 [3,2,2] 不會另外算成一組，因為這題只在意「組合」，不在意元素排列順序

二、解題想法：Backtracking
這題使用Backtracking（回溯）

我們可以把每一次選擇想成一條路：
選擇數字
↓
目前總和是否達到 target？
↓
沒有 → 繼續選
↓
超過 → 回頭
↓
達到 → 記錄答案

例如：target = 7
先選：[2]
目前總和為：2
還沒到 7，所以繼續選：[2,2]
總和：4
再選：[2,2,2]
總和：6
繼續選 2 就會變成：8
超過target，因此這條路不能繼續，要回溯
接著嘗試：[2,2,3]
剛好：2 + 2 + 3 = 7
就把這組答案加入結果

三、這題最重要的兩個條件

1. currentSum == target
   代表找到一組符合條件的答案：currentSum == target
   把目前組合加入result，然後返回

2. currentSum > target
   代表目前總和已經超過目標：currentSum > target
   這條路不可能得到正確答案，因此直接停止

這也是 Backtracking 很重要的一部分：不符合條件的路，就不要繼續往下探索

四、Java實作

五、Python實作

六、Java與Python比較

七、實作結果
Leetcode測試結果：Accepted

八、今日學習心得
今天練習的Combination Sum讓我更加理解Backtracking的使用方式。前幾天學習Permutations時，是透過used記錄哪些元素已經使用過，而今天的Combination Sum則是讓同一個元素可以重複使用，因此遞迴時不能直接把索引往後移，而是要繼續使用目前的索引。

這題最重要的地方是理解「選擇、探索、回溯」的流程。每選擇一個數字，就將它加入目前的組合並繼續往下搜尋；如果總和剛好等於target，就記錄答案；如果總和超過target，就停止這條路徑並回到上一層。

我也注意到，雖然同一個數字可以重複使用，但題目不希望因為順序不同而產生重複組合。因此利用start控制搜尋方向，可以避免產生[2,3,2]、[3,2,2]這類其實相同的組合。

透過 Java 和 Python 同時實作後，我發現 Backtracking 雖然剛開始看起來比較抽象，但只要掌握「做選擇 → 遞迴探索 → 撤銷選擇」這個流程，就能慢慢理解程式到底是怎麼把所有可能性找出來的。