LeetCode-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]

  源码：Java版本
  算法分析：时间复杂度O(n!)，空间复杂度O(n)
  

  ?

  public class Solution {
     public List
      
       > combinationSum2(int[] candidates,
  			int target) {
  		if (candidates == null) {
  			return null;
  		}
  		Set
       
        > results = new HashSet
        
         >(); Stack
         
           stack = new Stack
          
           (); Arrays.sort(candidates); DFS(candidates,0, target, stack, results); return new ArrayList
           
            >(results); } @SuppressWarnings(unchecked) private void DFS(int[] candidates,int start, int target, Stack
            
              stack, Set
             
              > results) { if (target == 0) { results.add((Stack
              
               ) (stack.clone())); } for (int i = start; i < candidates.length; i++) { stack.push(candidates[i]); if (target - candidates[i] >= 0) { DFS(candidates, i+1,target - candidates[i], stack, results); } stack.pop(); } } }
              
             
            
           
          
         
        
       
      

  
  

  ?