5ms JAVA solution


  • 3
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> ans=new ArrayList<List<Integer>>();    
        ch(candidates,target,0,new ArrayList<Integer>(),ans);
        return ans;
    }
    public void ch(int[] candidates,int remain,int rindex,List<Integer> tmp,List<List<Integer>> ans)
    {
        if(remain==0)
        {
            List<Integer> a=new ArrayList<Integer>(tmp);
            ans.add(a);
            return;
        }
        int entered=0; // get rid of duplicate combinations
        for(int i=rindex;i<candidates.length;i++)
        {
            if(entered!=candidates[i]) // get rid of duplicate combinations
            {
                if(remain-candidates[i]<0) break; //This line of code can reduce 7ms from execution time!
                tmp.add(candidates[i]);
                entered=candidates[i];
                ch(candidates,remain-candidates[i],i+1,tmp,ans);
                tmp.remove(tmp.size()-1); 
            }   
        }
    }

Log in to reply
 

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