Combination Sum Java Solution with detailed explanation


  • 0
    U

    Combination Sum is a classic depth first traversal problem.

    The general approach for this kind of problem are two key features
    Feature 1: build the recursive tree

    • clarify the level index ( in this example, it's represented by "i")
    • clarify how the children nodes are going to be represented

    Feature: build the masterResult and subResult

    • build the masterResult with conditional gate, then return ( in this example, the conditional gate for the masterResult is if(target == 0 )
    • build the subResult with conditional gate, then return (in this example, the conditional gate for the subResult is candidates[i] > target

    Below is the template in action, enjoy!

    public class Solution{
    	public List<List<Integer>> combinationSum(int[] candidates, int target) {
    	    List<List<Integer>> result = new ArrayList<>();
            List<Integer> subResult = new ArrayList<>();
    	   	//edge case 
    		if(candidates == null || candidates.length == 0){
    		    return result;
    		}
    		//main case
            Arrays.sort(candidates);
    		helper(candidates, target, result, subResult, 0);
    		return result;
    	}
    
    	private void helper(int[] candidates, int target,List<List<Integer>> result,
    	List<Integer> subResult, int level){
    	    //build masterResult with conditional gate
    		if(target == 0){
                result.add(new ArrayList<Integer>(subResult));
    			return;
    		}
    		//clarify the levelIndex, each level how to represent the children 
    		for(int i = level; i < candidates.length; i++){
    			// build subResult with conditional gate, return
                if(candidates[i] > target){
                    return;
                }
    			subResult.add(candidates[i]);
    			//recurisvely go deeper
    			helper(candidates, target - candidates[i], result, subResult, i);
    			subResult.remove(subResult.size()-1);
    		}
    	}
    }
    

Log in to reply
 

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