摘要：給定一個正整數(shù)數(shù)組元素?zé)o重復(fù)，給定目標(biāo)，找出組合的個數(shù)，使得組合中元素的和等于。數(shù)組元素可以重復(fù)使用遞歸調(diào)用循環(huán)中，對于第一題修改的起始位置即可但是。結(jié)果如果第一處修改成結(jié)果變?yōu)槿绻谝惶幮薷臑橐约暗诙幮薷臑榻Y(jié)果變?yōu)?/p>

Given a set of candidate numbers (C) (without duplicates) 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.
例如: [2, 3, 6, 7] and target 7

[
  [7],
  [2, 2, 3]
]

給定一個數(shù)組（元素?zé)o重復(fù)），和一個目標(biāo)值，找到所有組合，加起來等于目標(biāo)值。數(shù)組中的元素可以重復(fù)使用.
解法：

public class CombinationSum {
    public static List> combinationSum(int[] candidates, int target){
        Arrays.sort(candidates);
        List> result = new ArrayList<>();
        getResult(result, new ArrayList(), candidates, target, 0);
        return result;
    }

    private static void getResult(List> result, ArrayList current, int[] candidates, int target,
            int start) {
        if(target<0)    return;
        if(target==0){
            result.add(new ArrayList<>(current));
            return;
        }
        for(int i = start; i= candidates[i]; i++){
            current.add(candidates[i]);
            getResult(result, current, candidates, target-candidates[i], i);
            current.remove(current.size() - 1);
        }
    }
    public static void main(String[] args) {
        int[] nums = {2,3,6,7};
        System.out.println(combinationSum(nums, 7));
    }
}

給定一個數(shù)組（元素可以有重復(fù)），和一個目標(biāo)值，找到所有組合，加起來等于目標(biāo)值。數(shù)組中的元素不能重復(fù)使用。
例子: [10, 1, 2, 7, 6, 1, 5] and target 8

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

解法：

/**
 * 要去重，注意邊界，遞歸時(shí)候要加一
 */
public class CombinationSum2 {
    public List> combinationSum2(int[] candidates, int target) {
        List> result = new ArrayList<>();
        Arrays.sort(candidates);
        dfs(result, new ArrayList(), candidates, target, 0);
        return result;
    }
    
    private void dfs(List> result, ArrayList current, int[] candidates, int target, int start) {
        if(target < 0)  return;
        if(target == 0){
            result.add(new ArrayList(current));
            return;
        }
        for(int i = start; i= candidates[i]; i++){
            current.add(candidates[i]);
            dfs(result, current, candidates, target - candidates[i], i+1);    // 此處注意i+1,每個元素只能用一次，加一后在向下遞歸
            current.remove(current.size()-1);
            while(i < candidates.length - 1 && candidates[i] == candidates[i+1]) i++;    // 去重復(fù)（注意上面有i+1,這里要length-1，邊界問題）
        }
    }
    public static void main(String[] args) {
        int[] array = {10, 1, 2, 7, 6, 1, 5};
        int target = 8;
        System.out.println(new CombinationSum2().combinationSum2(array, target));
    }
}

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

給定K和N，從1--9中這幾個9個數(shù)字組合出來K個數(shù)，其和為N。1-9不能重復(fù)使用.

/**
 * 注意結(jié)束條件：size達(dá)到k值 并且 剩余值為0
 */
public class CombinationSum3 {
    public List> combinationSum3(int k, int n) {
        List> result = new ArrayList<>();
        dfs(result, new ArrayList(), k, n, 1);
        return result;
    }
    private void dfs(List> result, ArrayList current, int k, int remainder, int start){
        if(current.size() == k && remainder == 0){ //size達(dá)到k值 并且 剩余值為0
            result.add(new ArrayList<>(current));
            return ;
        }
        for(int i = start; i<=9 && remainder >= i; i++){
            current.add(i);
            dfs(result, current, k, remainder - i, i+1); // 不重復(fù)，i+1
            current.remove(current.size() - 1);
        }
    }
    public static void main(String[] args) {
        System.out.println(new CombinationSum3().combinationSum3(3, 15));
    }
}

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.

Follow up: What if negative numbers are allowed in the given array?
How does it change the problem? What limitation we need to add to the
question to allow negative numbers?
如果有負(fù)數(shù)，就不能讓數(shù)組中的元素重復(fù)使用。

給定一個正整數(shù)數(shù)組（元素?zé)o重復(fù)），給定目標(biāo)target，找出組合的個數(shù)，使得組合中元素的和等于target。數(shù)組元素可以重復(fù)使用.

public class CombinationSum4 {
    public int combinationSum4(int[] candidates, int target){
        List> result = new ArrayList<>();
        dfs(result, new ArrayList(), candidates, target, 0);
        return result.size();
    }
    
    private void dfs(List> result, ArrayList current, int[] candidates, int target, int start) {
        if(target < 0)    return;
        if(target == 0){
            result.add(new ArrayList<>(current));
            return;
        }
        for(int i = 0; i= candidates[i]; i++){
            current.add(candidates[i]);
            dfs(result, current, candidates, target-candidates[i], i);
            current.remove(current.size() - 1);
        }
    }
    public static void main(String[] args) {
        int[] arr = {1,2,3};
        System.out.println(new CombinationSum4().combinationSum4(arr, 4));
    }
}

遞歸調(diào)用循環(huán)中，對于第一題修改i的起始位置即可：i = 0
但是TLE。遞歸深度太深。
所以這個方法是不行的。
需要使用DP。

public int combinationSum4(int[] candidates, int target){
    Arrays.sort(candidates);
    int[] dp = new int[target + 1];
    dp[0] = 1;
    for(int i = 1; i i)    break;
            dp[i] += dp[i - curr];
        }
    }
    return dp[target];
}

有道面經(jīng)題目是一個修改版，也是返回組合個數(shù)即可，但是加了條件：去掉重復(fù)。
上面的例子：nums = [1, 2, 3] target = 4 ，返回 7.
The possible combination ways are: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)
這個題目要返回的是4，所有的組合是：(1, 1, 1, 1) (1, 1, 2) (1, 3) (2, 2) (3, 1)
變成第一題了：需要改變返回值，返回大小即可。

看一下這幾個的區(qū)別，輕微的改動，產(chǎn)生的不同結(jié)果：
以第一題Combination Sum I為基礎(chǔ)：

public class CombinationSum {
    public static List> combinationSum(int[] candidates, int target){
        Arrays.sort(candidates);
        List> result = new ArrayList<>();
        getResult(result, new ArrayList(), candidates, target, 0);
        return result;
    }
    
    private static void getResult(List> result, ArrayList current, int[] candidates, int target,
            int start) {
        if(target < 0)    return; // 是有可能小于0的
        if(target == 0){
            result.add(new ArrayList<>(current)); // 此處注意
            return;
        }
        // 注意點(diǎn)1
        for(int i = start; i= candidates[i]; i++){
            current.add(candidates[i]);
            getResult(result, current, candidates, target-candidates[i], i); // 注意點(diǎn)2
            current.remove(current.size() - 1);
        }
    }
    public static void main(String[] args) {
        int[] nums = {1,2,3};
        System.out.println(combinationSum(nums, 4));
    }
}

在上面的兩個注意點(diǎn)上：
第一題：數(shù)組（元素?zé)o重復(fù)），數(shù)組中的元素可以重復(fù)使用。結(jié)果

[[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2]]

如果第一處修改成 i = 0 結(jié)果變?yōu)椋?/p>

[[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1]]

如果第一處修改為 i = start 以及 第二處修改為 i+1 結(jié)果變?yōu)椋?/p>

[[1, 3]]