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

• 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();
}
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();
Collections.sort(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;
}``````

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