Recursive java solution


  • 8
    H
    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>();
                set.add(candidates[i]);
                result.add(set);
            }
    
            // 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){
                    list.add(0,candidates[i]);
                    result.add(list);
                } 
            }
        }
        
        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
    S
    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
    C
    This post is deleted!

  • 0
    C

    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(){...}

Log in to reply
 

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