鏈接：https://leetcode.com/problems/combination-sum/

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

題目描述

先說(shuō)一下題目：給定一個(gè)數(shù)組，里面只含有無(wú)重復(fù)的正整數(shù)，然后給定一個(gè)target，從數(shù)組里選取一些數(shù)，使其和為target，每個(gè)數(shù)可以選擇多次。求出所有這樣的組合。比如說(shuō)：
數(shù)組：【2，3，6，7】
target：7
結(jié)果：【2，2，3】和【7】

數(shù)組：【2，3，5】
target：8
結(jié)果：【2，2，2，2】、【2，3，3】和【3，5】

思路

以【2，3，6，7】為例，target = 7
先對(duì)數(shù)組進(jìn)行排序。
首先【2】，還剩下 7 - 2 = 5 > 0，
再取2，變?yōu)?code>【2，2】，還剩下 5 - 2 = 3 > 0，
再取2，變?yōu)?code>【2，2，2】，還剩下 3 - 2 = 1 > 0，
再取2，變?yōu)?code>【2，2，2，2】，還剩下1 - 2 = -1 < 0，由于所有的數(shù)都是正數(shù)，所以回溯，去掉最后一個(gè)2，變?yōu)?code>【2，2，2】，還剩下1。
此時(shí)開(kāi)始取下一個(gè)數(shù)：
取3，變?yōu)?code>【2，2，2，3】還剩下1 - 3 = -2 < 0，再回溯，去掉最后一個(gè)3，變?yōu)?code>【2，2，2】，還剩下1。
我們發(fā)現(xiàn)，在【2，2，2】的情況下，【2，2，2，6】、【2，2，2，7】都不滿足。

再回溯，變?yōu)?code>【2，2】，還剩下3，取下一個(gè)數(shù)：
取3，變?yōu)?code>【2，2，3】，3 - 3 = 0，符合條件。
之后再取3及后面的數(shù)都不滿足: [2，2，3，3】、【2，2，3，6】、【2，2，3，7】。
回溯，去掉最后一個(gè)數(shù)3，變?yōu)?code>【2，2】，剩下3 > 0
此時(shí)再取3后面的數(shù)都不滿足，【2，2，6】、【2，2，7】都不滿足。

再回溯，變?yōu)?code>【2】，剩下5，取下一個(gè)數(shù)：
取6，變?yōu)?code>【2，6】，5 - 6 < 0，回溯，
再取7，變?yōu)?code>【2，7】不符合，回溯。
變?yōu)?code>【2】，此時(shí)已經(jīng)取完，再回溯，變?yōu)榭?code>【】。

取下一個(gè)數(shù)，變?yōu)?code>【3】，7 - 3 = 4 > 0，
再取3，【3，3】，4-3=1>0，
再取3，【3，3，3】，1-3=-2<0，回溯。刪去最后一個(gè)3，變?yōu)?code>【3，3】。
此時(shí)取后面的數(shù)都不行。再回溯，刪除最后一個(gè)3，變?yōu)?code>【3】。
取下一個(gè)6，【3，6】，7-3-6<0，回溯。變?yōu)?code>【3】。再回溯，變?yōu)?code>【】。
取下一個(gè)6，【6】，7-6=1>0，
再取6，【6，6】，1-6<0，回溯，再回溯，變?yōu)榭?code>【】。
去下一個(gè)7，【7】，7-7=0，符合。
。。。

代碼

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    //res用來(lái)存放所有的結(jié)果
    List<List<Integer>> res = new LinkedList<>();
    //對(duì)數(shù)組進(jìn)行排序
    Arrays.sort(candidates);
    helper(candidates, new LinkedList<Integer>(), res, 0, target);
    return res;
}

//list代表臨時(shí)選取的數(shù)組成的列表，start是開(kāi)始迭代的index，remain=target減去list里所有數(shù)的和。
private void helper(int[] nums, List<Integer> list, List<List<Integer>> res, int start, int remain){
    //remain小于0，說(shuō)明list里面所有的數(shù)的和已經(jīng)大于target，直接返回
    if(remain < 0) return;
    //remain等于0，說(shuō)明list里面所有的數(shù)的和等于target，將該數(shù)組復(fù)制一份放進(jìn)結(jié)果集中。
    if(remain == 0){
        res.add(new LinkedList<>(list));
        return;
    }
    //remain大于0，還需要往list里面加數(shù)，從start開(kāi)始加。
    for(int i = start; i < nums.length; ++i){
        list.add(nums[i]);
        //因?yàn)檫x取的數(shù)可以重復(fù)，所以這里還是i，而不是i+1。
        helper(nums, list, res, i, remain - nums[i]);
        list.remove(list.size() - 1);
    }
}

可以看到，helper方法在兩種情況下return：remain < 0及remain == 0，因?yàn)閿?shù)組中的數(shù)已經(jīng)排序、唯一且大于0，所以這兩種情況出現(xiàn)之后，再往list里面加數(shù)都不滿足list里元素的和等于target，所以返回之后，去掉list里的最后一個(gè)數(shù)（list.remove(list.size() - 1)），從下一個(gè)數(shù)繼續(xù)遍歷。

舉一反三

這道題還有一個(gè)變形，鏈接：https://leetcode.com/problems/combination-sum-ii/
這道題的不同點(diǎn)就是：
1、給定數(shù)組中的數(shù)可以重復(fù)
2、每個(gè)數(shù)只能選一次
比如說(shuō)：

Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

直接看代碼：

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new LinkedList<>();
        Arrays.sort(candidates);
        helper(candidates, new LinkedList<Integer>(), res, 0, target);
        return res;
    }
    
    private void helper(int[] nums, List<Integer> list, List<List<Integer>> res, int start, int remain){
        if(remain < 0) return;
        if(remain == 0){
            res.add(new LinkedList<>(list));
        }
        for(int i = start; i < nums.length; ++i){
            if(i > start && nums[i] == nums[i - 1]) {
                //System.out.println("i:" + i + " num: " + nums[i]);
                continue;
            }
            list.add(nums[i]);
            //list.forEach(System.out::print);
            //System.out.println();
            //由于每個(gè)數(shù)只能用一次，所以這里直接 i + 1，
            helper(nums, list, res, i + 1, remain - nums[i]);
            list.remove(list.size() - 1);
        }
    }

不同的地方有兩點(diǎn)：
一個(gè)是helper(nums, list, res, i + 1, remain - nums[i])，在選取一個(gè)數(shù)之后，再選取下一個(gè)，這里是i + 1。
另一個(gè)是if(i > start && nums[i] == nums[i - 1]) continue;，這里是因?yàn)閿?shù)組中有重復(fù)的數(shù)，而我們的結(jié)果集中不能存在一樣的選取組合。比如說(shuō)[10,1,2,7,6,1,5] target = 8，[1，2，5]是一個(gè)選擇方式，但是因?yàn)?有兩個(gè)，所以我們只能取1個(gè)。

自己覺(jué)得邏輯比較亂的話可以自己打印一下關(guān)鍵信息，好好理一理。