Java o(nlogn) recursive simple


  • -2
    R
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        //sort the candidates
        Arrays.sort(candidates);
        for(int index=0; index<candidates.length; index++){
            temp.add(candidates[index]);
            combinationSumRecursive(candidates, target-candidates[index], result,temp,index+1);
            temp.remove(temp.size()-1);
        }
        return result;
    }
    private void combinationSumRecursive(int[] candidates, int target,List<List<Integer>> result, List<Integer> temp,int index){
        if(target<0){
            return;
        }
        if(target==0){
            // check duplicated
            List<Integer> tmp = new ArrayList<>(temp);
            if(!result.contains(tmp)){
                result.add(tmp);
            }
            return;
        }
        for(; index<candidates.length; index++){
            temp.add(candidates[index]);
            combinationSumRecursive(candidates, target-candidates[index], result,temp,index+1);
            temp.remove(temp.size()-1);
        }
        return;
    }

Log in to reply
 

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