Combination Sum.java

public class Solution {
    /**
     * @param candidates: A list of integers
     * @param target:An integer
     * @return: A list of lists of integers
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // write your code here
        List<List<Integer>> result = new ArrayList<>();
        if (candidates == null || candidates.length == 0) {
            return result;
        }
        
        List<Integer> combination = new ArrayList<>();
        Arrays.sort(candidates);
        combinationSumHelper(candidates, target, 0, result, combination);
        
        return result;
    }
    
    public void combinationSumHelper(int[] candidates, int target, int pos, List<List<Integer>> result, List<Integer> combination) {
        if (target == 0) {
            result.add(new ArrayList<Integer>(combination));
            return;
        }
        for (int i = pos; i < candidates.length; i++) {
            if (target >= candidates[i]) {
                combination.add(candidates[i]);
                int restTarget = target - candidates[i];
                combinationSumHelper(candidates, restTarget, i, result, combination);
                combination.remove(combination.size() - 1);
            } 
        }
    }
}