Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:
For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]
1 public class Solution { 2 public List<List<Integer>> combinationSum2(int[] num, int target) { 3 int[] candidates = num; 4 List<List<Integer>> resSet = new ArrayList<List<Integer>>(); 5 List<Integer> curRes = new ArrayList<Integer>(); 6 if (candidates.length==0) return resSet; 7 Arrays.sort(candidates); 8 int cur=0,end=candidates.length-1; 9 for (int i=0;i<candidates.length;i++) 10 if (candidates[i]>target){ 11 end = i-1; 12 break; 13 } 14 15 16 sumRecur(candidates,cur,end,target,resSet,curRes); 17 18 return resSet; 19 20 } 21 22 23 public void sumRecur(int[] candidates, int cur, int end, int valLeft, List<List<Integer>> resSet, List<Integer> curRes){ 24 if (valLeft==0){ 25 List<Integer> temp = new ArrayList<Integer>(); 26 temp.addAll(curRes); 27 resSet.add(temp); 28 return; 29 } 30 31 if (cur>end) return; 32 33 int newLeft = valLeft; 34 int curLen = curRes.size(); 35 int nextIndex = cur; 36 while (nextIndex<=end && candidates[nextIndex]==candidates[cur]) nextIndex++; 37 38 for (int i=cur;i<nextIndex;i++) 39 if (newLeft>=candidates[i]){ 40 curRes.add(candidates[i]); 41 newLeft -= candidates[i]; 42 sumRecur(candidates,nextIndex,end,newLeft,resSet,curRes); 43 } else 44 break; 45 46 while (curRes.size()!=curLen) curRes.remove(curRes.size()-1); 47 48 sumRecur(candidates,nextIndex,end,valLeft,resSet,curRes); 49 } 50 }
原文：http://www.cnblogs.com/lishiblog/p/4111918.html