LeetCode 39 Combination Sum

https://leetcode.com/problems/combination-sum/

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        //pick one element unlimited times => make up sum equals to target
        //broute force find target
        
        List<List<Integer>> answer = new ArrayList<>();
        List<Integer> current = new ArrayList<>();
        
        findCombinationSum(candidates, target, 0, 0, current, answer);
        return answer;
        
    }
    
    private void findCombinationSum(int[] candidates, int target, int sum, int index, List<Integer> current, List<List<Integer>> answer){
        if (sum > target){
            return;
        }
        if (sum == target){
            answer.add(new ArrayList<>(current));
            return;
        }
        
        for (int i = index; i < candidates.length; i++){
            current.add(candidates[i]);
            
            //not i + 1 since we can reuse the candidate
            findCombinationSum(candidates, target, sum + candidates[i], i, current, answer);
            
            current.remove(current.size() - 1);
        }
    }
    
    //2,3,6,7  sum 0
    //^.       sum2
    //  ^.     sum3
    //.   ^.   sum6
    //.     ^. sum 7 =>answer
    //^x2.     sum 4
    //. ^x2.   sum 6
    //^.^      sum 5
    //^x2^.    sum 7 => answer
}