题目：

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]

思路：递归，不断地尝试余下的值。

package sum;import java.util.ArrayList;import java.util.Arrays;import java.util.List;public class CombinationSum {    public List
     
      
       > combinationSum(int[] candidates, int target) {        Arrays.sort(candidates);        int len = removeDuplicates(candidates);        List
       
        
         > res = new ArrayList
         
          
           >(); List
           
             record = new ArrayList
            
             (); combine(candidates, 0, len, res, record, target); return res; } private void combine(int[] nums, int start, int end, List
             
              
               > res, List
               
                 record, int target) { for (int i = start; i < end; ++i) { List
                
                  newRecord = new ArrayList
                 
                  (record); newRecord.add(nums[i]); int sum = sum(newRecord); int rem = target - sum; if (rem == 0) { res.add(newRecord); } else if (rem > 0 && rem >= nums[i]) { combine(nums, i, end, res, newRecord, target); } else if (rem < 0) { break; } } } private int sum(List
                  
                    record) { int sum = 0; for (int i : record) sum += i; return sum; } private int removeDuplicates(int[] nums) { int n = nums.length; int j = 0; for (int i = 1; i < n; ++i) { if (nums[i] != nums[i - 1]) { nums[++j] = nums[i]; } } return j + 1; } public static void main(String[] args) { // TODO Auto-generated method stub int[] nums = { 1, 2, 2, 3, 6, 7 }; CombinationSum c = new CombinationSum(); List
                   
                    
                     > res = c.combinationSum(nums, 7); for (List
                     
                       l : res) { for (int i : l) System.out.print(i + "\t"); System.out.println(); } }}