# My thoughts and solution to the problem -Java

• Hello, I've solve the problem and I am here to give back to the community. Basically the question is pretty straight forward. I've approached the problem with sorting the array first, and keeping the current value and make recursive call to check for target - current value. Any suggestion on how I can make this code better is much appreciated. Thank you.

``````public class Solution {
public List<List<Integer>> combinationSum2(int[] num, int target) {
if(num.length==0) return new ArrayList<List<Integer>>();
Arrays.sort(num); //sort the array of num so it's easier to manage
List<List<Integer>> result = helper(num,target,0);
if(result==null) return new ArrayList<List<Integer>>();
return result;
}
public List<List<Integer>> helper(int[] num, int target, int index)
{
if(index>=num.length||num[index]>target) return null; //return null if you hit the end
ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();
ArrayList<Integer> temp = new ArrayList<Integer>();
Set<List<Integer>> s = new HashSet<List<Integer>>(); //check if there is no duplicates
for(int i = index;i<num.length;i++)
{
//if num[i]> target you dont need to check the rest.
//but it's break here because you still want to keep the rest of the result.
if(num[i]>target) break;
temp = new ArrayList<Integer>();
//if it's found the rest of the numbers can be trimed, save some time on complexity
if(num[i]==target)
{
return result;
}
ArrayList<List<Integer>> t = (ArrayList)helper(num,target-num[i],i+1);
//t is the temporary ArrayList of the result of your recursion call
// you want to add the value of your current num[i] in the beginning of each
// returned List<Integer> and add it to result if it's not duplicated.
if(t!=null)
{
for(List<Integer> a:t)
{
if(!s.contains(a)) //make sure there is no duplicates
{
}
}
}
}
return result;
}
}``````

• the s.contains(a) takes O(n) time to check all the elements in s, so it may create time limit exceed problem.
Such as in 3Sum problem (quite similar to this problem).

This Combination sum does not has time limit exceed problem, I think it is because this Combination sum
takes O(n!) time itself.

I am not sure what I thought is right. Just for your reference.
Below is my way to avoid to use contains. It is quite similar to your solution

``````public List<List<Integer>> combinationSum2(int[] num, int target) {
Arrays.sort(num);
return combinationSum(num,target,0);
}
public List<List<Integer>> combinationSum(int[] num, int target, int index){
List<List<Integer>> result=new ArrayList<List<Integer>>();
if(target<=0) return result; //all the numbers all positive..no need to check left has 0 or negitive number
int previouscheck=Integer.MIN_VALUE;
for(int i=index;i<num.length;i++){
if(previouscheck==num[i]) continue; // if the same value num[i] has been checked before..skip it
previouscheck=num[i];
if(num[i]>target) break; // all left are bigger than target..
if(num[i]==target){
List<Integer> cur=new ArrayList<Integer>();
return result;
}
List<List<Integer>> lastreturn=combinationSum(num,target-num[i],i+1);
if(!lastreturn.isEmpty()){
for(List<Integer> cur:lastreturn){