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

  • 0

    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();
        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(); 
        	   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(); 
                           if(!isExist(tmpRes, list)) tmpRes.add(list);
        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;
    	return true;

Log in to reply

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