题目
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1：
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]
示例 2：
输入：candidates = [2,3,5], target = 8,
所求解集为：
[
[2,2,2,2],
[2,3,3],
[3,5]
]
提示：
1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate 中的每个元素都是独一无二的。
1 <= target <= 500
思路
这一题很容易想到用递归来解决，采用递归就要确定递归的边界和操作。
先看递归操作，很简单，就是遍历candidates数组，每次从中取出一个元素加入存储当前结果的集合中。
再看递归边界，边界为：
- 当结果集合的元素和大于target时，直接返回
- 当结果集合的元素和等于target时，将结果集合加入总结果的集合再返回
但是直接这样写会出现一个问题：总结果集中会出现重复元素。观察递归树：
image
每次添加元素时，只需要从当前元素的后面开始考虑，前面都已经枚举过了。所以还需要递归当前元素的下标。
代码
class Solution {
private List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
ArrayList<Integer> res = new ArrayList<>();
cal(0, candidates, res, target, 0);
return result;
}
private void cal(int start, int[] candidates, ArrayList<Integer> res, int target, int sum) {
if(sum > target)
return;
if(sum == target) {
result.add(new ArrayList<>(res));//这里要构造一个新的
return;
}
for (int i = start; i < candidates.length; i++) {
res.add(candidates[i]);
cal(i, candidates, res, target, sum + candidates[i]);
res.remove(res.size() - 1);
}
}
}
注意在添加元素时，要new数组。
