力扣-39.组合总和

题目链接

39.组合总和

class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();void backtracking(int[] nums, int target, int sum, int start) {if (sum > target)return;if (sum == target) {res.add(new ArrayList<>(path));return;}for (int i = start; i < nums.length; i++) {sum += nums[i];path.add(nums[i]);backtracking(nums, target, sum, i);	//这里是i不是i+1因为可以重复使用同一数字sum -= nums[i];path.remove(path.size() - 1);}}public List<List<Integer>> combinationSum(int[] candidates, int target) {backtracking(candidates, target, 0, 0);return res;}
}

小结：还是源于标准的模板，由于[2,2,3]和[2,3,2]算一种，所以引入start变量防止重复，还有传入参数i而不是i+1，最后注意sum > target要结束递归。