A recursive yet efficient Java solution with explanation


  • 7
    L

    The problem is a bit like N-queen problem, which is to say that we just need to enumerate all the possible solution recursively to get the final result.

    First of all, we need to sort the array, to ensure the combination to be unique and also the numbers in the combination to be listed in a non-descending order.

    Then, we define a recursive function with the signature as:

    combinationSum(int [] candidates, LinkedList vector, int start, int target)
    

    where “candidates” is the list that we could take numbers from, “vector” is the list of combination that we have accumulated so far, “start” is the starting point at which we could take numbers from forwards (no backwards), and “target” is the rest sum that we need to achieve.

    As a recursive function, the bottom cases for the combinationSum() are:

    1). The value of the “start” element is equal to the “target”, we then find a combination, so just add the “start” element to the “vector” and output the result.

    2). The value of the “start” element is greater than the “target”, then it is impossible to find the combination onwards, because the “candidates” list is sorted and all the following elements would be greater than the “target” as well.

    Given the above recursive function, we could solve the problem by calling the function for each candidate starting from the start point.
    For each candidates, we first try to add the candidate into the “vector”, and then again starting from this candidate, we call the combinationSum() function to obtain the result for the new “target” afterwards.

    Here is the code.

    private List<List<Integer>> res = new LinkedList<List<Integer>>();
    
    private void combinationSum(int [] candidates, LinkedList<Integer> vec,
    							int start, int target){
    	
    	for(int i=start; i<candidates.length; ++i){
    		if(candidates[i] < target){
    			LinkedList<Integer> newVec = new LinkedList<Integer>();
    			newVec.addAll(vec);
    			newVec.add(candidates[i]);
    
    			// Try a new combination, one could repeat itself again, so start from "i", instead of "i+1" 
    			combinationSum(candidates, newVec, i, target-candidates[i]);				
    		}else if(candidates[i] == target){
    
    			// Found a combination
    			LinkedList<Integer> newVec = new LinkedList<Integer>();
    			newVec.addAll(vec);
    			newVec.add(candidates[i]);
    			res.add(newVec);
    		}else{
    			// candidates[i] > target, no need to continue
    			break;
    		}
    	}
    }
    
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
    	Arrays.sort(candidates);
    	LinkedList<Integer> vec = new LinkedList<Integer>();
    	this.combinationSum(candidates, vec, 0, target);
    	return res;
    }

Log in to reply
 

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