# My Solution In JAVA

• Generally speaking it is a DFS solution

``````public class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
if (candidates==null||candidates.length==0) return Collections.emptyList();//Or throw exception();

Arrays.sort(candidates);

for (int i=0,len=candidates.length;i<len;i++){

if (i>0&&candidates[i]==candidates[i-1]) continue; //Avoid duplicates;
combinationSumHelper(candidates,i,target,work,results);//DFS
}
return results;
}
//Use DFS
private void combinationSumHelper(int[] candidates,int index, int target,LinkedList<Integer> work,List<List<Integer>> results){
//Compare candidates[index] and target;
//If equals, terminate the search,return result
//If candidates[index] > target, terminate the search, no result
//Otherwise, study rest of elements.
if (candidates[index]>target){
return;
}else if (candidates[index]==target){//Update the
work.removeLast();
return;
}
for (int i=index+1,len=candidates.length;i<len;i++){
if (i>index+1&&candidates[i]==candidates[i-1]) continue;//Avoid dulipcates
if (candidates[i]<=target-candidates[index]){
combinationSumHelper(candidates,i,target-candidates[index],work,results);
}
}
work.removeLast();
}
}``````

• Your method is concise but elusive, could you please give more tips? Thank you so much.

• Hello qian2 I have updated my solution with a DFS one. This one is even more consice and clear.

• Thank you, the recursive solution is pretty concise, my solution is recursive too, but I don't know how to solve it iteratively, can you do that?

• I can do it in a BFS way. It is less effecient. Let me modify my original solution tomorrow.

• ``````public class Solution {
public List<List<Integer>> combinationSum2(int[] num, int target) {

if (num == null || num.length == 0){
return Collections.emptyList();
}
Arrays.sort(num);

int gap,last;
//Make a graph by BFS
while (!diff.isEmpty()) {
gap = diff.poll();
//System.out.print(diff+" ");
list = lists.poll();

last = (!list.isEmpty())?list.get(list.size()-1):-1;

for (int i = last+1; i < num.length; i++) {
if (i>0&&num[i-1]==num[i]&&i-1>last) continue;//Avoid duplicates and visited

if (gap>=(num[i]+num[i])) {//if gap>=num[i] && gap<=2*num[i], it is impossible to make the target

} else if (gap==num[i]){
}else
continue;
}
}
//Make the result
for (List<Integer> pre:path){
ArrayList<Integer> result= new ArrayList<Integer>();
for (Integer i:pre)