|
| 1 | +packagemedium; |
| 2 | +importjava.util.*; |
| 3 | + |
| 4 | +importutils.CommonUtils; |
| 5 | +publicclassCombinationSumII { |
| 6 | + |
| 7 | + |
| 8 | +publicList<List<Integer>>combinationSum2(int[]candidates,inttarget) { |
| 9 | +List<List<Integer>>result =newArrayList(); |
| 10 | +Arrays.sort(candidates); |
| 11 | +helper(candidates,target,0,newArrayList(),result); |
| 12 | +returnresult; |
| 13 | + } |
| 14 | + |
| 15 | +voidhelper(int[]candidates,inttarget,intstart,List<Integer>curr,List<List<Integer>>result){ |
| 16 | +if(target >0){ |
| 17 | +for(inti =start;i <candidates.length &&target >=candidates[i];i++){ |
| 18 | +if(i >start &&candidates[i] ==candidates[i-1])continue;//skip duplicates, this is one difference from Combination Sum I |
| 19 | +curr.add(candidates[i]); |
| 20 | +helper(candidates,target -candidates[i],i+1,curr,result);//i+1 is the other difference from Combination Sum I |
| 21 | +curr.remove(curr.size()-1); |
| 22 | + } |
| 23 | + }elseif(target ==0){ |
| 24 | +List<Integer>temp =newArrayList(curr); |
| 25 | +result.add(temp); |
| 26 | + } |
| 27 | + } |
| 28 | + |
| 29 | + |
| 30 | +publicstaticvoidmain(String...args){ |
| 31 | +CombinationSumIItest =newCombinationSumII(); |
| 32 | +int[]candidates =newint[]{10,1,2,7,6,1,5}; |
| 33 | +inttarget =8; |
| 34 | +List<List<Integer>>result =test.combinationSum2(candidates,target); |
| 35 | +CommonUtils.printIntegerList(result); |
| 36 | + } |
| 37 | + |
| 38 | + |
| 39 | +} |