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] 

本题与上题Combination Sum类似，只是添加了去重部分

input	output	expected
[1,1], 1	[[1],[1]]	[[1]]

1 public class Solution { 2     public ArrayList
     
      
       > combinationSum2(int[] num, int target) { 3         // Start typing your Java solution below 4         // DO NOT write main() function 5         ArrayList
       
        
         > result = new ArrayList
         
          
           >(); 6 int len = num.length, depth = 0; 7 if(len == 0){ 8 return result; 9 }10 ArrayList
           
             output = new ArrayList
            
             ();11 int sum = 0;12 Arrays.sort(num);13 generate(result, output, sum, depth, len, target, num);14 return result;15 }16 17 public void generate(ArrayList
             
              
               > result, ArrayList
               
                 output, int sum,18 int depth, int len, int target, int[] candidates){19 if(sum > target){20 return;21 }22 if(sum == target){23 ArrayList
                
                  tmp = new ArrayList
                 
                  ();24 tmp.addAll(output);25 result.add(tmp);26 return;27 }28 29 for(int i = depth; i < len; i++){30 sum += candidates[i];31 output.add(candidates[i]);32 generate(result, output, sum, i + 1, len, target, candidates);33 sum -= output.get(output.size() - 1);34 output.remove(output.size() - 1);35 while(i < len - 1 && candidates[i] == candidates[i+1])36 i++;37 }38 }39 }