-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCombination Sum
More file actions
27 lines (23 loc) · 918 Bytes
/
Combination Sum
File metadata and controls
27 lines (23 loc) · 918 Bytes
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
//target=2, candidates=[1, 2]
public class Solution {
private LinkedList<LinkedList<Integer>> results=new LinkedList<LinkedList<Integer>>();
public LinkedList<LinkedList<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
LinkedList<Integer> solution=new LinkedList<Integer>();
helper(candidates, 0, target, solution);
return results;
}
private void helper(int[] candidates, int k, int target, LinkedList<Integer> solution) {
if (target<0) return;
if (target==0) {
LinkedList<Integer> res=new LinkedList<Integer>(solution);
results.add(res);
return;
}
for (int i=k; i<candidates.length; i++) {
solution.add(candidates[i]);
helper(candidates, i, target-candidates[i], solution);
solution.remove(solution.size()-1);
}
}
}