My JAVA recursive solution


  • 0
    J
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        return combinationSum(candidates,target,candidates.length-1);
    }
    private List<List<Integer>> combinationSum(int[] candidates, int target,int end){
        List<List<Integer>> res=new ArrayList<List<Integer>>();
        while(end>=0&&candidates[end]>target) end--;
        if(end<0) return res;
        for(int i=end;i>=0;i--){
            List<List<Integer>> sums=combinationSum(candidates,target-candidates[i],i);
            if(target==candidates[i]) sums.add(new ArrayList<Integer>());
            for(List<Integer> sum:sums){
                sum.add(candidates[i]);
                res.add(sum);
            }
        }
        return res;
    }

Log in to reply
 

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