Simple Java 22ms Recursion Solution


  • 0
    Q

    The point for combination is to find the termination condition. In this solution, the target is reduced by amount of the current value. The return condition is when target is smaller or equal to 0.

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> rt = new ArrayList();
        if(candidates.length == 0 || target <= 0){
            return rt;
        }
        helper(candidates, target, rt, new ArrayList<Integer>(), 0);
        return rt;
    }
    
    public void helper(int[] candidates, int target, List<List<Integer>> rt, ArrayList<Integer> path, int start){
        if(target < 0){
            return;
        }
        if(target == 0){
            rt.add(new ArrayList(path));
            return;
        }
        for(int i = start; i < candidates.length; i++){
            path.add(candidates[i]);
            helper(candidates, target - candidates[i], rt, path, i);
            path.remove(path.size() - 1);
        }
    }
    

Log in to reply
 

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