2.25力扣-回溯组合总和

39. 组合总和 - 力扣（LeetCode）

一：Java

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

为什么删去：if(sum>target) return ; 语句，会报错  --  栈溢出

因为递归是i开始，而非i+1,如果没有这个 if(sum>target) return 语句，达不到sum==target的条件，会一直在i处累加，最后一直递归没有结束。