# Simple java solution

• ``````List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
helper(candidates, 0, target, new ArrayList<Integer>());
return res;
}

private void helper(int[] can, int start, int target,List<Integer> each) {
for (int i = start; i < can.length; i++) {
List<Integer> temp = new ArrayList<>(each);
if (can[i] == target) {
break;
} else if (can[i] < target) {
helper(can, i, target - can[i], new ArrayList<>(temp));
} else {break;}
}
return;
}``````

• Nice Solution! I solved this problem with the same idea. However, instead of using res as a field, i made it as a local variable in my program:

• if candidates[i] == target, add it and return;

• if candidates[i] > target, it means we can break this loop since no combination starting from this element could sum up to target;

• if candidates[i] < target, we can recursively find the solution starting from the same element but different target number (which is current target - candidates[i]).

`````` public class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
if (candidates == null || candidates.length == 0) return result;
Arrays.sort(candidates);
return combinationSum(candidates, target, 0);
}

private List<List<Integer>> combinationSum(int[] candidates, int target, int start) {
List<List<Integer>> result = new ArrayList<>();
for (int i = start; i < candidates.length; i++) {
if (candidates[i] == target) {
List<Integer> temp = new ArrayList<>();
return result;
}
if (candidates[i] > target) return result;
List<List<Integer>> next = combinationSum(candidates, target - candidates[i], i);
if (next.size() == 0) continue;
for (List<Integer> list : next) list.add(0, candidates[i]);
}
return result;
}
``````

}

• Change this line :

``````helper(can, i, target - can[i], new ArrayList<>(temp));
``````

to:

``````helper(can, i, target - can[i], temp);
``````

The performance will be much better.

• Your answer is not correct if the input is [2,2,3,6,7]. it's strange that it can past the online test.

• And if you change the loop to (i.e. get rid of `temp` copy):

``````    if (can[i] == target) {
each.remove(each.size()-1);
break;
} else if (can[i] < target) {
helper(can, i, target - can[i], each);
each.remove(each.size()-1);
} else {break;}
``````

You should have even better performance.

• @coco_sally The problem statement says: "Given a set of candidate numbers".

As StefanPochmann told me in a similar occasion: GIGO.

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