# Recursive java solution

• ``````public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates); // sort the array, so the result could be increasing order
List<List<Integer>> result = new ArrayList<List<Integer>>();

for(int i = 0; i < candidates.length; i++){
// target smaller than current number, jump the current and rest of numbers
if(target < candidates[i]) continue;

// if target is equal to the current number,add it to a new list and add that list to result
else if(target == candidates[i]){
List<Integer> set = new ArrayList<Integer>();
}

// if the target is smaller the current number,call this function again
else{
// use modified array which not includes those numbers that before i to eliminate the duplicates
int[] array = Arrays.copyOfRange(candidates,i,candidates.length);

// call this function. pass the new target and modified array.
List<List<Integer>> temp = combinationSum(array, target - candidates[i]);

// for each list in the return list, add current number in the front of list, then add it to result
// attention that if return list is null, this enhanced for loop will not perform.
for(List<Integer> list:temp){
}
}
}

return result;
}
``````

They key point is passing new target and modified array. Pass the modified array to make sure no duplicates set. If the new target could not find a match number, the return list will be null, thus this null list will not be added to the result list.

• ``````if(target < candidates[i]) continue;
``````

this line can be:

``````if(target < candidates[i]) return result;
``````

because the numbers later are always larger than candidates[i] so we don't have to continue going. And this may be a little faster :-)

• This post is deleted!

• You can change code that only execute sort() once in the whole execution, that will improve the performance.

``````public List<List> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
return combinationSumHelper(candidates, target);
}
private combinationSumHelper(){...}``````

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