鏈接：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.
題目描述
先說一下題目：給定一個數(shù)組薇搁，里面只含有無重復的正整數(shù)欧漱，然后給定一個target，從數(shù)組里選取一些數(shù)，使其和為target稠集，每個數(shù)可以選擇多次。求出所有這樣的組合续捂。比如說：
數(shù)組：【2眷蜈，3，6隅俘，7】
target：7
結果：【2邻奠，2笤喳，3】和【7】
數(shù)組：【2，3碌宴，5】
target：8
結果：【2杀狡，2，2贰镣，2】呜象、【2，3碑隆，3】和【3恭陡，5】
思路
以【2，3上煤，6休玩，7】為例，target = 7
先對數(shù)組進行排序劫狠。
首先【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ù)弥激，所以回溯进陡，去掉最后一個2，變?yōu)?code>【2微服，2趾疚，2】，還剩下1。
此時開始取下一個數(shù)：
取3糙麦，變?yōu)?code>【2辛孵，2，2赡磅，3】還剩下1 - 3 = -2 < 0魄缚，再回溯，去掉最后一個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斜做，取下一個數(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】。
回溯绽慈，去掉最后一個數(shù)3恨旱，變?yōu)?code>【2，2】坝疼，剩下3 > 0
此時再取3后面的數(shù)都不滿足搜贤，【2，2钝凶，6】仪芒、【2，2耕陷，7】都不滿足掂名。
再回溯，變?yōu)?code>【2】哟沫，剩下5饺蔑，取下一個數(shù)：
取6，變?yōu)?code>【2嗜诀，6】膀钠，5 - 6 < 0，回溯裹虫，
再取7肿嘲，變?yōu)?code>【2，7】不符合筑公，回溯雳窟。
變?yōu)?code>【2】，此時已經取完匣屡，再回溯封救，變?yōu)榭?code>【】。
取下一個數(shù)捣作，變?yōu)?code>【3】誉结，7 - 3 = 4 > 0，
再取3券躁，【3惩坑，3】掉盅，4-3=1>0，
再取3以舒，【3趾痘，3，3】蔓钟，1-3=-2<0永票，回溯。刪去最后一個3滥沫，變?yōu)?code>【3侣集，3】。
此時取后面的數(shù)都不行兰绣。再回溯世分，刪除最后一個3，變?yōu)?code>【3】狭魂。
取下一個6罚攀，【3党觅，6】雌澄，7-3-6<0，回溯杯瞻。變?yōu)?code>【3】镐牺。再回溯，變?yōu)?code>【】魁莉。
取下一個6睬涧，【6】，7-6=1>0旗唁，
再取6畦浓，【6，6】检疫，1-6<0讶请，回溯，再回溯屎媳，變?yōu)榭?code>【】夺溢。
去下一個7，【7】烛谊，7-7=0风响，符合。
丹禀。状勤。鞋怀。
代碼
public List<List<Integer>> combinationSum(int[] candidates, int target) {
//res用來存放所有的結果
List<List<Integer>> res = new LinkedList<>();
//對數(shù)組進行排序
Arrays.sort(candidates);
helper(candidates, new LinkedList<Integer>(), res, 0, target);
return res;
}
//list代表臨時選取的數(shù)組成的列表，start是開始迭代的index荧降，remain=target減去list里所有數(shù)的和接箫。
private void helper(int[] nums, List<Integer> list, List<List<Integer>> res, int start, int remain){
//remain小于0，說明list里面所有的數(shù)的和已經大于target朵诫，直接返回
if(remain < 0) return;
//remain等于0辛友，說明list里面所有的數(shù)的和等于target，將該數(shù)組復制一份放進結果集中剪返。
if(remain == 0){
res.add(new LinkedList<>(list));
return;
}
//remain大于0废累，還需要往list里面加數(shù)，從start開始加脱盲。
for(int i = start; i < nums.length; ++i){
list.add(nums[i]);
//因為選取的數(shù)可以重復邑滨，所以這里還是i，而不是i+1钱反。
helper(nums, list, res, i, remain - nums[i]);
list.remove(list.size() - 1);
}
}
可以看到掖看，helper方法在兩種情況下return：remain < 0及remain == 0，因為數(shù)組中的數(shù)已經排序面哥、唯一且大于0哎壳，所以這兩種情況出現(xiàn)之后，再往list里面加數(shù)都不滿足list里元素的和等于target尚卫，所以返回之后归榕，去掉list里的最后一個數(shù)（list.remove(list.size() - 1)），從下一個數(shù)繼續(xù)遍歷吱涉。
舉一反三
這道題還有一個變形刹泄，鏈接：https://leetcode.com/problems/combination-sum-ii/
這道題的不同點就是：
1、給定數(shù)組中的數(shù)可以重復
2怎爵、每個數(shù)只能選一次
比如說：
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();
//由于每個數(shù)只能用一次特石，所以這里直接 i + 1，
helper(nums, list, res, i + 1, remain - nums[i]);
list.remove(list.size() - 1);
}
}
不同的地方有兩點：
一個是helper(nums, list, res, i + 1, remain - nums[i])鳖链，在選取一個數(shù)之后姆蘸，再選取下一個，這里是i + 1撒轮。
另一個是if(i > start && nums[i] == nums[i - 1]) continue;乞旦，這里是因為數(shù)組中有重復的數(shù)，而我們的結果集中不能存在一樣的選取組合题山。比如說[10,1,2,7,6,1,5] target = 8兰粉，[1，2顶瞳，5]是一個選擇方式玖姑，但是因為1有兩個愕秫，所以我們只能取1個。
自己覺得邏輯比較亂的話可以自己打印一下關鍵信息焰络，好好理一理戴甩。
