I solve it with dp solution but it ends up with a long runtime 42ms, how to improve it?


  • 0
    Y

    I thought it was a dp problem and I tried to store previous list for following computations. But this solution can not avoid to check if a new list exists in the result list, which makes the whole logic kind of not clean, anyone knows how to improve it?

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList();
        Arrays.sort(candidates);
        if(target < candidates[0]) return res;
        HashMap<Integer, List<List<Integer>>> map = new HashMap();
        for(int i = 1; i < candidates[0];i++){
            map.put(i, new ArrayList<List<Integer>>());
        }
        for(int i = candidates[0]; i<= target; i++){
        	List<List<Integer>> tmpRes = new ArrayList();
           for(int j = 0; j<candidates.length;j++){
        	   if(i == candidates[j]){
        		   ArrayList<Integer> list = new ArrayList(); 
        		   list.add(i);
        		   tmpRes.add(list);
        	   }
        	   else if(i > candidates[j]){
                   if(map.get(i - candidates[j]).size() != 0){
                       for(List<Integer> l : map.get(i - candidates[j])){
                    	   ArrayList<Integer> list = new ArrayList(); 
                           list.add(candidates[j]);
                           list.addAll(l);
                           Collections.sort(list);
                           if(!isExist(tmpRes, list)) tmpRes.add(list);
                       }                	   
                   }
               }else{
            	   break;
               }
           }
           map.put(i,tmpRes);
        }
        return map.get(target);
    }
    public boolean isExist(List<List<Integer>> lists, List<Integer> l){
    	for(List<Integer> list : lists){
    		if(equals(list, l)) return true;  		
    	}
    	return false;
    }
    public boolean equals(List<Integer> l1, List<Integer> l2){
    	if(l1.size() != l2.size()) return false;
    	int i = 0;
    	while(i < l1.size()){
    		if(l1.get(i)!=l2.get(i)) return false;
    		i++;
    	}
    	return true;
    }

Log in to reply
 

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