別眨眼網

求組合數。和順序無關。

2，3

3，2 是一個組合

for 迴圈的目的是 遍歷每個可能的元素。

start 索引的目的是 從集合的哪個位置開始遍歷。如果不能重複利用集合元素，那麼 遞迴的時候就要start + 1 ，

回溯的過程是 遞迴語句的後面，

需要和回溯前 做對稱的操作。

path。add（nums［i］）；

sum += nums［i］；

// 遞迴

dfs（nums， res， path， target， sum， i）；

// 回溯

sum -= nums［i］；

path。remove（path。size（） - 1）；

程式碼最佳化一下：

class Solution { List> res = new ArrayList<>（）； List path = new ArrayList<>（）； public List> combinationSum（int［］ candidates， int target） { if（candidates。length == 0）{ return res； } dfs（candidates， target， 0， 0）； // 不傳遞路徑和結果 return res； } // 回溯 private void dfs（int［］ nums， int target， int sum， int start）{ // 遞迴終止條件 if（sum > target）{ return； }else if（sum == target）{ res。add（new ArrayList<>（path））；// 加入結果陣列 } // 遍歷集合，做遞迴 for（int i = start； i < nums。length； i++）{ // i 是集合的元素， start 是起始位置， start - candidate。length - 1； // 做操作 path。add（nums［i］）； sum += nums［i］； // 遞迴 // dfs（nums， res， path， target， sum， i+ 1）； dfs（nums， target， sum， i）； // 回溯 sum -= nums［i］； path。remove（path。size（） - 1）； } }}

另外一種寫法，

dfs（nums， target

， sum + nums［i］，

i）； //

把sum 的變化寫在遞迴函數里面

// 遍歷集合，做遞迴 for（int i = start； i < nums。length； i++）{ // i 是集合的元素， start 是起始位置， start - candidate。length - 1； // 做操作 path。add（nums［i］）； // sum += nums［i］； // 遞迴 dfs（nums， target， sum + nums［i］， i）； // 把sum 的變化寫在遞迴函數里面。 // 回溯 // sum -= nums［i］； path。remove（path。size（） - 1）； }

加油！