LeetCode-Combination Sum

题目：https://oj.leetcode.com/problems/combination-sum/

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

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 2,3,6,7 and target 7,
  A solution set is:
  [7]
[2, 2, 3]

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

  public class Solution {
     public List
      
       > combinationSum(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,target - candidates[i], stack, results); } stack.pop(); } } }
              
             
            
           
          
         
        
       
      

  代码解释：

  1. 因为要升序，所有先对数组进行排序;

  2. 因为要升序，所以下次遍历的开始位置是当前位置，所以添加了start变量；

  3. 结果要无重复，故先用set收集结果去重。