Java 4ms DFS Solution, VERY EASY understand!!!


  • 1
    P

    This is still a "Subset 2" problem

    public List<List<Integer>> combinationSum2(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;
            if( i != pos && candidates[i] == candidates[i-1]) continue;
            
            path.add(candidates[i]);
            helper(rst, path, sum+candidates[i],candidates,target, i+1);
            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.