Recursive java solution

  • 8
    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
                // 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.

  • 2
    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 :-)

  • 0
    This post is deleted!

  • 0

    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) { 
       return combinationSumHelper(candidates, target); 
    private combinationSumHelper(){...}

Log in to reply

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