|
| 1 | +packageAlgorithms.combination; |
| 2 | + |
| 3 | +importjava.util.ArrayList; |
| 4 | +importjava.util.Arrays; |
| 5 | +importjava.util.List; |
| 6 | + |
| 7 | +publicclassCombinationSum { |
| 8 | +publicList<List<Integer>>combinationSum(int[]candidates,inttarget) { |
| 9 | +List<List<Integer>>ret =newArrayList<List<Integer>>(); |
| 10 | +if (candidates ==null ||candidates.length ==0) { |
| 11 | +returnret; |
| 12 | + } |
| 13 | + |
| 14 | +List<Integer>path =newArrayList<Integer>(); |
| 15 | + |
| 16 | +// we should sort the candidates than do it. in this case we can get a non-descending order. |
| 17 | +Arrays.sort(candidates); |
| 18 | + |
| 19 | +combinationSum(candidates,target,path,ret,0); |
| 20 | +returnret; |
| 21 | + } |
| 22 | + |
| 23 | +publicvoidcombinationSum(int[]candidates,inttarget,List<Integer>path,List<List<Integer>>ret,intindex) { |
| 24 | +if (target ==0) { |
| 25 | +// add the current set into the result. |
| 26 | +ret.add(newArrayList<Integer>(path)); |
| 27 | +return; |
| 28 | + } |
| 29 | + |
| 30 | +if (target <0) { |
| 31 | +return; |
| 32 | + } |
| 33 | + |
| 34 | +intlen =candidates.length; |
| 35 | +for (inti =index;i <len;i++) { |
| 36 | +intnum =candidates[i]; |
| 37 | +path.add(num); |
| 38 | +combinationSum(candidates,target -num,path,ret,i); |
| 39 | +path.remove(path.size() -1); |
| 40 | + } |
| 41 | + } |
| 42 | +} |