解题思路
一道非常经典的回溯题目。根据回溯三部曲：
- 确定回溯函数的返回值和参数
- 确定递归的终止条件
- 确定单层递归的逻辑
- 回溯函数一般返回值都是void, 参数由于涉及到加和问题，定义个curSum 用于实时更新当前路径的累加值，定义target 传递目标值。startIndex用于限制取数的范围，防止重复。
- 当
curSum大于target时, 直接return。当curSum==target收货答案。 - 注意由于元素可以重复选取，
process(nums, i, curSum, target), 这里的i不需要+1。下一层取数，依然从当前元素的位置开始选取。
代码
class Solution {
List<Integer> path = new ArrayList<>();
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
if (candidates == null) return res;
process(candidates, 0, 0, target);
return res;
}
public void process(int[] nums, int startIndex, int curSum, int target) {
if (curSum > target) return;
if (curSum == target) {
res.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i < nums.length; i++) {
path.add(nums[i]);
curSum += nums[i];
process(nums, i, curSum, target);
path.removeLast();
curSum -= nums[i];
}
}
}