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("Added to answer");
System.out.println("Now rec is: " + rec);
res.add(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("Added to rec");
rec.add(arr[i]);
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.
Here is a reference link.
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){
res.add(new ArrayList<>(rec));
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
rec.add(arr[i]);
search(arr, tar - arr[i], res, rec, i);
int test = rec.get(rec.size()-1);
rec.remove(rec.size()-1);
}
//System.out.println("Finally, the res is: " + res);
// return res;
}
}