# Combination Sum

This is a problem in leetcode.

To solve this problem, I decide to use recursion on it:

``````class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {

List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> rec = new ArrayList<Integer>();

search( candidates, target, res, rec, 0);

return res;
}

private void search(int[] arr, int tar, List<List<Integer>>res, List<Integer>rec, int start){

// check
if(tar == 0){
System.out.println("Now rec is: " + rec);
System.out.println("Now res is: " + res);
return;
}

// for loop
for( int i = start; i < arr.length; i++ ){
System.out.println("The element is: " + arr[i]);
// check if current element > target
if(arr[i] > tar){
System.out.println("Break");
break; // should use break to skip this round
}

// if not, then add this element to our rec

System.out.println("Rec call");
search(arr, tar - arr[i], res, rec, i);

System.out.println("Remove current element");
int test = rec.get(rec.size()-1);
System.out.println("Kick out: " + test);
rec.remove(rec.size()-1);

}

//System.out.println("Finally, the res is: " + res);
// return res;
}
}``````

Code above has some bugs to fix, but I want to explain my main thought first.
I crate two ArrayList, one is rec for temporary result, and res for final result.
In recursion function search, I will check the value of target first, if it equal to 0, I will add my rec to res, which means I have found the result.
Otherwise, i will check each element in array and sum them up till the sum trigger the condition I mention above.
Unfortunately, I still have two bugs here.
First one is more obviously, that is I need to sort the array first.
Second one is that I can't add my rec directly, I should use new ArrayList<>(rec). The reason is that I should crate a new independence ArrayList to store my current rec and protect it from being modified later.

And the final version is below:

``````
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {

Arrays.sort(candidates);

List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> rec = new ArrayList<Integer>();

search( candidates, target, res, rec, 0);

return res;
}

private void search(int[] arr, int tar, List<List<Integer>>res, List<Integer>rec, int start){

// check
if(tar == 0){

return;
}

// for loop
for( int i = start; i < arr.length; i++ ){

// check if current element > target
if(arr[i] > tar){

break; // should use break to skip this round
}

// if not, then add this element to our rec