回溯法---组合总和

题目：

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

思路：

全局变量result存储结果集，path存储某一组合

第一步：确定参数与返回值。参数为candidates数组，target，sum（path数组中现有值之和），startIndex（遍历的candidates数组下标起始），无返回值

第二步：确定终止条件。当target=sum时，获取到一个组合，将组合加入到结果集中

第三步：确定单层递归逻辑。for循环遍历candidates数组，从startIndex到candidates数组的最后一个元素。进行剪枝优化操作，当sum+candidates[i]>target时，就不必进行下去了。for循环里的步骤就是：更新sum，更新path，递归调用，回溯。

代码：

    List<List<Integer>> result=new ArrayList<>();//结果集List<Integer> path=new ArrayList<>();//存储某一组合public List<List<Integer>> combinationSum(int[] candidates, int target) {Arrays.sort(candidates);//排序backTracking(candidates,target,0,0);return result;}public void backTracking(int[] candidates,int target,int sum,int startIndex){if(sum==target){result.add(new ArrayList<>(path));return;}for(int i=startIndex;i<candidates.length&&sum+candidates[i]<=target;i++){sum+=candidates[i];path.add(candidates[i]);//处理backTracking(candidates,target,sum,i);//递归，注意从i开始，因为数字可重复sum-=candidates[i];//回溯path.remove(path.size()-1);}}