Very easy-understanding Java solution with recursion

• Main idea:

• Iteratively choose the elements in the given candidates.
• Recursively construct the result with backtracking.

AC code:

``````public class Solution {
List<List<Integer>> ret;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
ret = new ArrayList<List<Integer>>();
int len = candidates.length;
List<Integer> tmp = new ArrayList<Integer>();
List<Integer> rem = new ArrayList<Integer>();
func(tmp,rem,target);
return ret;
}
private void func(List<Integer> tmp, List<Integer> rem, int target){
if(getSum(tmp)==target){
return ;
}
if(getSum(tmp)<target){
for(int i=0;i<rem.size();i++){
List<Integer> tmp1 = new ArrayList<Integer>(tmp);
// Stop for useless combination to save time
if(getSum(tmp1)>target) break;
List<Integer> rem1 = new ArrayList<Integer>();
for(int j=i;j<rem.size();j++)
func(tmp1, rem1, target);
}
}
}
private int getSum(List<Integer> tmp){
int sum=0;
for(int x:tmp)
sum+=x;
return sum;
}
}
``````

While, can anyone told me why my solution is slower than the average? (The pervasive solution is to deduct the target, while mine is to add up to the target. I think the idea and process is the same...). Thanks for you advice~

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.