LeetCode-Combination Sum II

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();
  		}
  	}
  }