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

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.解題思路
對(duì)數(shù)組進(jìn)行排序，每次加入第i個(gè)數(shù)后，target就減去這個(gè)數(shù)，并作為新的target，進(jìn)行遞歸。如果target<0，則說明本次無解；如果target=0，則將本序列組合加入結(jié)果集中。因?yàn)閿?shù)字可以repeated，所以每次遞歸都從第i個(gè)開始。
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.解題思路
本題與上一題的區(qū)別就是同一個(gè)數(shù)字在一個(gè)組合中只能出現(xiàn)一次，那么就需要考慮下面兩種情況：
1） 每次遞歸開始的index要加1；
2）在同一個(gè)for循環(huán)中，即針對(duì)同一個(gè)target，需要排除重復(fù)的數(shù)字。因?yàn)閿?shù)組已經(jīng)事先進(jìn)行排序，所以只要判斷下當(dāng)前數(shù)字是否和前一個(gè)數(shù)字相等即可。
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.解題思路

其實(shí)本題與題I非常相似，只是加入了組合元素的個(gè)數(shù)限制k。題意其實(shí)就是從數(shù)組[1,2,...,9]中選出k個(gè)數(shù)，使得sum等于target。唯獨(dú)一點(diǎn)與題I的區(qū)別就是這里每個(gè)數(shù)只能選一遍，所以每次遞歸都從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.解題思路
受前面三題的啟發(fā)，很容易就想到繼續(xù)用遞歸進(jìn)行回溯，但是發(fā)現(xiàn)Time Exceed Limit. 再仔細(xì)看題目，發(fā)現(xiàn)其實(shí)是動(dòng)態(tài)規(guī)劃。給定一個(gè)數(shù)組，求和為target的組合個(gè)數(shù)，那我們定義狀態(tài)dp[i]表示和為i的數(shù)字組合的個(gè)數(shù)，那么狀態(tài)轉(zhuǎn)移就是dp[i]=dp[i-nums[0]]+dp[i-nums[1]]+...+dp[i-nums[n-1]];當(dāng)然前提是i大于nums[]。
其實(shí)說到這，我們發(fā)現(xiàn)這其實(shí)和動(dòng)態(tài)規(guī)劃的經(jīng)典題目CoinChange找零錢非常相似，但找零錢相對(duì)復(fù)雜一些，因?yàn)檎伊沐X需要得到所有組合中擁有最少元素的組合的元素?cái)?shù)量，即最少的紙幣數(shù)目；但這一題只需要求出所有的組合數(shù)即可。
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];
    }
}