39. Combination Sum

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ret=new ArrayList<List<Integer>>();
        Arrays.sort(candidates);
        generateCombination(new ArrayList<Integer>(), 0, ret, candidates, target);
        return ret;
    }
    private void generateCombination(List<Integer> list, int idx, List<List<Integer>> combs, int[] candidates, int target){
        if(target==0)
        {
            combs.add(new ArrayList<Integer>(list));
            return;
        }
        if(target<0||idx>=candidates.length)
            return;
        generateCombination(list, idx+1, combs, candidates, target);
        list.add(candidates[idx]);
        generateCombination(list, idx, combs, candidates, target-candidates[idx]);
        list.remove(list.size()-1);
    }    
}