摘要：給定一個正整數數組元素無重復，給定目標，找出組合的個數，使得組合中元素的和等于。數組元素可以重復使用遞歸調用循環中，對于第一題修改的起始位置即可但是。結果如果第一處修改成結果變為如果第一處修改為以及第二處修改為結果變為

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

給定一個數組（元素無重復），和一個目標值，找到所有組合，加起來等于目標值。數組中的元素可以重復使用.
解法：

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));
    }
}

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

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

解法：

/**
 * 要去重，注意邊界，遞歸時候要加一
 */
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++;    // 去重復（注意上面有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個數字組合出來K個數，其和為N。1-9不能重復使用.

/**
 * 注意結束條件：size達到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達到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); // 不重復，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?
如果有負數，就不能讓數組中的元素重復使用。

給定一個正整數數組（元素無重復），給定目標target，找出組合的個數，使得組合中元素的和等于target。數組元素可以重復使用.

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));
    }
}

遞歸調用循環中，對于第一題修改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];
}

有道面經題目是一個修改版，也是返回組合個數即可，但是加了條件：去掉重復。
上面的例子：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)
變成第一題了：需要改變返回值，返回大小即可。

看一下這幾個的區別，輕微的改動，產生的不同結果：
以第一題Combination Sum I為基礎：

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;
        }
        // 注意點1
        for(int i = start; i= candidates[i]; i++){
            current.add(candidates[i]);
            getResult(result, current, candidates, target-candidates[i], i); // 注意點2
            current.remove(current.size() - 1);
        }
    }
    public static void main(String[] args) {
        int[] nums = {1,2,3};
        System.out.println(combinationSum(nums, 4));
    }
}

在上面的兩個注意點上：
第一題：數組（元素無重復），數組中的元素可以重復使用。結果

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

如果第一處修改成 i = 0 結果變為：

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

如果第一處修改為 i = start 以及 第二處修改為 i+1 結果變為：

[[1, 3]]