Combination Sum II

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:

• All numbers (including target) will be positive integers.
• Elements in a combination (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ â‰¤ a₂ â‰¤ … ≤ a_k).
• The solution set must not contain duplicate combinations.

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] 

Solution: slightly modified from Combination Sum.

Java语言: CombinationSumII

01 public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
02     ArrayList<ArrayList<Integer>> results=new ArrayList<ArrayList<Integer>>();
03     if(num.length==0)
04         return results;
05     Arrays.sort(num);
06     ArrayList<Integer> temp=new ArrayList<Integer>();
07     doCombine(results, temp, num, target, 0);
08     return results;
09 }
10 
11 public void doCombine(ArrayList<ArrayList<Integer>> results, ArrayList<Integer> temp, int [] num, int target, int start)
12 {
13     for(int i=start;i<num.length;i++)
14     {
15         if(target==num[i])
16         {
17             temp.add(num[i]);
18             ArrayList<Integer> out=new ArrayList<Integer>(temp);
19             if(!results.contains(out))
20                 results.add(out);
21           
22         }
23         else if(target>num[i])
24         {
25             temp.add(num[i]);
26             doCombine(results, temp, num, target-num[i], i+1);
27         }
28         else
29         {
30             return;
31         }
32       
33         int size=temp.size();
34         if(size>0)
35             temp.remove(size-1);
36     }
37 }