# Combination Sum Java Solution with detailed explanation

• 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){
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;
}