【LeetCode】No.39 Combination Sum
链接：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.
题目描述
先说一下题目：给定一个数组，里面只含有无重复的正整数，然后给定一个target，从数组里选取一些数，使其和为target，每个数可以选择多次。求出所有这样的组合。比如说：
数组：【2，3，6，7】
target：7
结果：【2，2，3】和【7】
数组：【2，3，5】
target：8
结果：【2，2，2，2】、【2，3，3】和【3，5】
思路
以【2，3，6，7】为例，target = 7
先对数组进行排序。
首先【2】，还剩下 7 - 2 = 5 > 0，
再取2，变为【2，2】，还剩下 5 - 2 = 3 > 0，
再取2，变为【2，2，2】，还剩下 3 - 2 = 1 > 0，
再取2，变为【2，2，2，2】，还剩下1 - 2 = -1 < 0，由于所有的数都是正数，所以回溯，去掉最后一个2，变为【2，2，2】，还剩下1。
此时开始取下一个数：
取3，变为【2，2，2，3】还剩下1 - 3 = -2 < 0，再回溯，去掉最后一个3，变为【2，2，2】，还剩下1。
我们发现，在【2，2，2】的情况下，【2，2，2，6】、【2，2，2，7】都不满足。
再回溯，变为【2，2】，还剩下3，取下一个数：
取3，变为【2，2，3】，3 - 3 = 0，符合条件。
之后再取3及后面的数都不满足: [2，2，3，3】、【2，2，3，6】、【2，2，3，7】。
回溯，去掉最后一个数3，变为【2，2】，剩下3 > 0
此时再取3后面的数都不满足，【2，2，6】、【2，2，7】都不满足。
再回溯，变为【2】，剩下5，取下一个数：
取6，变为【2，6】，5 - 6 < 0，回溯，
再取7，变为【2，7】不符合，回溯。
变为【2】，此时已经取完，再回溯，变为空【】。
取下一个数，变为【3】，7 - 3 = 4 > 0，
再取3，【3，3】，4-3=1>0，
再取3，【3，3，3】，1-3=-2<0，回溯。删去最后一个3，变为【3，3】。
此时取后面的数都不行。再回溯，删除最后一个3，变为【3】。
取下一个6，【3，6】，7-3-6<0，回溯。变为【3】。再回溯，变为【】。
取下一个6，【6】，7-6=1>0，
再取6，【6，6】，1-6<0，回溯，再回溯，变为空【】。
去下一个7，【7】，7-7=0，符合。
。。。
代码
public List<List<Integer>> combinationSum(int[] candidates, int target) {
//res用来存放所有的结果
List<List<Integer>> res = new LinkedList<>();
//对数组进行排序
Arrays.sort(candidates);
helper(candidates, new LinkedList<Integer>(), res, 0, target);
return res;
}
//list代表临时选取的数组成的列表，start是开始迭代的index，remain=target减去list里所有数的和。
private void helper(int[] nums, List<Integer> list, List<List<Integer>> res, int start, int remain){
//remain小于0，说明list里面所有的数的和已经大于target，直接返回
if(remain < 0) return;
//remain等于0，说明list里面所有的数的和等于target，将该数组复制一份放进结果集中。
if(remain == 0){
res.add(new LinkedList<>(list));
return;
}
//remain大于0，还需要往list里面加数，从start开始加。
for(int i = start; i < nums.length; ++i){
list.add(nums[i]);
//因为选取的数可以重复，所以这里还是i，而不是i+1。
helper(nums, list, res, i, remain - nums[i]);
list.remove(list.size() - 1);
}
}
可以看到，helper方法在两种情况下return：remain < 0及remain == 0，因为数组中的数已经排序、唯一且大于0，所以这两种情况出现之后，再往list里面加数都不满足list里元素的和等于target，所以返回之后，去掉list里的最后一个数（list.remove(list.size() - 1)），从下一个数继续遍历。
举一反三
这道题还有一个变形，链接：https://leetcode.com/problems/combination-sum-ii/
这道题的不同点就是：
1、给定数组中的数可以重复
2、每个数只能选一次
比如说：
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();
//由于每个数只能用一次，所以这里直接 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])，在选取一个数之后，再选取下一个，这里是i + 1。
另一个是if(i > start && nums[i] == nums[i - 1]) continue;，这里是因为数组中有重复的数，而我们的结果集中不能存在一样的选取组合。比如说[10,1,2,7,6,1,5] target = 8，[1，2，5]是一个选择方式，但是因为1有两个，所以我们只能取1个。
自己觉得逻辑比较乱的话可以自己打印一下关键信息，好好理一理。
