-
Notifications
You must be signed in to change notification settings - Fork 0
/
Combination Sum
29 lines (29 loc) · 1.26 KB
/
Combination Sum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
Arrays.sort(candidates);
helpler(result, new ArrayList<Integer>(), candidates, 0, target);
return result;
}
private void helpler(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> path, int[] candidates, int start, int target){
if(target<0 || start >= candidates.length)
return;
if(target == 0) //only when all the integers add up to target, add the set
{
ArrayList<Integer> temp = new ArrayList<Integer>(path); //avoid Output Limit Exceeded
result.add(temp);
}
else{
for(int i=start; i<candidates.length; i++)
{
if(candidates[i] > target)
break;
path.add(candidates[i]);
helpler(result, path, candidates, i, target-candidates[i]);
path.remove(path.size()-1); //empty the ArrayList for next use
}
}
}
}