摘要：解題思路對數組進行排序，每次加入第個數后，就減去這個數，并作為新的，進行遞歸。如果，則說明本次無解如果，則將本序列組合加入結果集中。題意其實就是從數組中選出個數，使得等于。

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

1.解題思路
對數組進行排序，每次加入第i個數后，target就減去這個數，并作為新的target，進行遞歸。如果target<0，則說明本次無解；如果target=0，則將本序列組合加入結果集中。因為數字可以repeated，所以每次遞歸都從第i個開始。
2.代碼

public class Solution {
    List> res=new ArrayList>();
    public List> combinationSum(int[] candidates, int target) {
        if(candidates.length==0) return res;
        Arrays.sort(candidates);
        combine(candidates,target,0,new ArrayList());
        return res;
    }
    private void combine(int[] candidates, int target, int index,List pre){
         if(target<0) return;
         if(target==0){
             res.add(pre);
             return;
         }
         for(int i=index;i cur=new ArrayList(pre);
             cur.add(candidates[i]);
             combine(candidates,target-candidates[i],i,cur);
             
         }
            
    }
}

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

1.解題思路
本題與上一題的區別就是同一個數字在一個組合中只能出現一次，那么就需要考慮下面兩種情況：
1） 每次遞歸開始的index要加1；
2）在同一個for循環中，即針對同一個target，需要排除重復的數字。因為數組已經事先進行排序，所以只要判斷下當前數字是否和前一個數字相等即可。
2.代碼

public class Solution {
    List> res=new ArrayList>();
    public List> combinationSum2(int[] candidates, int target) {
        if(candidates.length==0) return res;
        Arrays.sort(candidates);
        combineHelper(candidates,0,target,new ArrayList());
        return res;
    }
    private void combineHelper(int[] candidates,int index,int target,List pre){
        if(target<0) return;
        if(target==0){
            res.add(pre);
            return;
        }
        for(int i=index;iindex&&candidates[i]==candidates[i-1]) continue;
            List cur=new ArrayList(pre);
            cur.add(candidates[i]);
            combineHelper(candidates,i+1,target-candidates[i],cur);
                
            
        }
    }
}

Combination Sum III
Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

1.解題思路

其實本題與題I非常相似，只是加入了組合元素的個數限制k。題意其實就是從數組[1,2,...,9]中選出k個數，使得sum等于target。唯獨一點與題I的區別就是這里每個數只能選一遍，所以每次遞歸都從i+1開始。

2.代碼

public class Solution {
    List> res =new ArrayList>();
    public List> combinationSum3(int k, int n) {
        if(k==0||n==0) return res;
        int[] nums={1,2,3,4,5,6,7,8,9};
        combine(nums,0,n,k,new ArrayList());
        return res;
    }
    private void combine(int[] nums,int index,int target,int k,List pre){
        if(target<0) return;
        if(target==0&&k==0){
            res.add(pre);
            return;
        }
        for(int i=index;i cur=new ArrayList(pre);
            cur.add(nums[i]);
            combine(nums,i+1,target-nums[i],k-1,cur);
        }
    }
}

Combination Sum IV
Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

1.解題思路
受前面三題的啟發，很容易就想到繼續用遞歸進行回溯，但是發現Time Exceed Limit. 再仔細看題目，發現其實是動態規劃。給定一個數組，求和為target的組合個數，那我們定義狀態dp[i]表示和為i的數字組合的個數，那么狀態轉移就是dp[i]=dp[i-nums[0]]+dp[i-nums[1]]+...+dp[i-nums[n-1]];當然前提是i大于nums[]。
其實說到這，我們發現這其實和動態規劃的經典題目CoinChange找零錢非常相似，但找零錢相對復雜一些，因為找零錢需要得到所有組合中擁有最少元素的組合的元素數量，即最少的紙幣數目；但這一題只需要求出所有的組合數即可。
CoinChange可參考 https://segmentfault.com/a/11...

2.代碼

public class Solution {
    public int combinationSum4(int[] nums, int target) {
        if(nums.length==0||target==0) return 0;
        int[] dp=new int[target+1];
        dp[0]=1;
        for(int i=1;i<=target;i++){
           for(int n:nums){
               if(i>=n){
                   dp[i]+=dp[i-n];
               }
           }
        }
        return dp[target];
    }
}