Leetcode/combinationSum.java at master · tanglu/Leetcode · GitHub

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
30
31
32
33
34
35
36
37
38
39
40
41
publicclassSolution {
voiddfs(int [] candidates, inttarget, ArrayList<Integer> array, ArrayList<ArrayList<Integer>> ret) {
if(target==0) {
ret.add(array);
return;
 }

for(inti=0;i<candidates.length;i++) {

if(array.size()>0) {
inttmp = array.get(array.size() - 1);
if(candidates[i]<=target&&candidates[i]>=tmp) {
ArrayList<Integer> array_next = newArrayList<Integer>(array);
array_next.add(candidates[i]);
dfs(candidates, target - candidates[i], array_next, ret);
 }

 } else {
if(candidates[i]<=target) {
ArrayList<Integer> array_next = newArrayList<Integer>(array);
array_next.add(candidates[i]);
dfs(candidates, target - candidates[i], array_next, ret);
 }
 }
 }

 }

publicArrayList<ArrayList<Integer>> combinationSum(int[] candidates, inttarget) {
ArrayList<ArrayList<Integer>> ret = newArrayList<ArrayList<Integer>>();

if(candidates==null||candidates.length==0) {
returnret;
 }
ArrayList<Integer> array = newArrayList<Integer>();

dfs(candidates, target, array, ret);

returnret;
 }
}