Java 5ms DFS VERY EASY understand solution


  • 0
    P

    In fact this is very similar to "Subset" backtracking problem.

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> rst = new ArrayList<>();
        if(candidates == null || candidates.length == 0){
            return rst;
        }
        
        Arrays.sort(candidates);
        helper(rst, new ArrayList<>(),0,candidates,target,0);
        return rst;
    }
    
    public void helper(List<List<Integer>> rst, List<Integer> path, int sum, int[] candidates, int target, int pos){
        if(sum == target){
            rst.add(new ArrayList<>(path));
            return;
        }
        
        for(int i=pos; i<candidates.length; i++){
            if(sum+candidates[i] > target) break;
            path.add(candidates[i]);
            helper(rst, path, sum+candidates[i], candidates, target, 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.