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();}}
}