DFS Java solution


  • 3
    M
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        ArrayList<Integer> sublist = new ArrayList<Integer>();
        dfs(candidates, target, 0, candidates.length, sublist, list);
        return list;
    }
    
    public void dfs(int[] candidates, int remainValue, int start, int length, ArrayList<Integer> sublist, List<List<Integer>> list){
        if(remainValue < 0 ){
            return;
        }
        if(remainValue == 0){
            list.add(sublist);
            return;
        }
        for(int i = start;  i < length; i++){
            int NextNumStartIndex = i;
            ArrayList<Integer> temp = new ArrayList<Integer>();
            temp.addAll(sublist);
            temp.add(candidates[i]);
            
            if(remainValue < candidates[i]) break;
            
            dfs(candidates, remainValue - candidates[i], NextNumStartIndex, length, temp, list);
        }
    }

Log in to reply
 

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