Day 72

題目描述（終于理順回溯了）

思路

這里還是基于模板來說明代碼思路

void backtracking(參數) {if (終止條件) {存放結果;return;}for (選擇 : 本層集合中的元素) {處理節點;backtracking(路徑, 選擇列表); // 遞歸撤銷處理; // 回溯}
}

對于主要函數的作用就是用來聲明結果集，臨時集以及調用函數的，不贅述了。
進入主要的函數代碼，
首先是終止條件，當我們獲取到的總和值大于等于target的時候就可以終止了（由于限制了元素值都是正整數），這里只有等于target才將其加入到結果集。
其次進入循環，這里回溯前后，有兩步要做，第一步添加元素到臨時集，第二步總和值增加。
最后回溯結束記得復原。
于是有了以下做法，但是這么做是有問題的。
出現問題的原因在于，我沒有控制循環的起始值就會導致以下重復的清空如 2 2 3 和3 2 2，那我們如何規避這種情況呢？見下一段代碼。

class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>>res = new ArrayList<List<Integer>>();List<Integer>te = new ArrayList<Integer>();back(te,res,0,target,candidates);return res;}public void back(List<Integer>te,List<List<Integer>>res,int sum,int target,int[]candidates){if(sum>=target){if(sum==target)res.add(new ArrayList<Integer>(te));return;}for(int i=0;i<candidates.length;i++){te.add(candidates[i]);sum+=candidates[i];back(te,res,sum,target,candidates);sum-=candidates[i];te.removeLast();}}
}

這里在上面代碼的基礎上進行修改，出現重復的原因在于，由于本題不限制元素使用次數，并且元素不重復，因此在我們首次進入遞歸循環一次時，就獲取了第一個元素所有組合總和的情況了。
同理我們聚焦到最高層遞歸的第二個循環，這里回溯還回到第一個元素，那就會出現重復的情況。
我們知道了問題的存在，如何解決了呢？
很簡單，使用一個start參數，在進行回溯時，只接著遍歷start以及start以后的元素即可。

class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>>res = new ArrayList<List<Integer>>();List<Integer>te = new ArrayList<Integer>();back(te,res,0,target,candidates,0);return res;}public void back(List<Integer>te,List<List<Integer>>res,int sum,int target,int[]candidates,int start){if(sum>=target){if(sum==target)res.add(new ArrayList<Integer>(te));return;}for(int i=start;i<candidates.length;i++){te.add(candidates[i]);sum+=candidates[i];back(te,res,sum,target,candidates,i);sum-=candidates[i];te.removeLast();}}
}