Open youngyangyang04 opened 3 months ago
private void backtracking(int[] nums, int target, int sum, int start) {
if(sum == target){
paths.add(new ArrayList<>(path));
return;
}
for(int i = start; i < nums.length && sum + nums[i] <= target; i++){
sum += nums[i];
path.add(nums[i]);
backtracking(nums, target, sum, i);
sum -= nums[i];
path.remove(path.size() - 1);
}
}
// 深度1: backtracking([2,3,6,7], 7, 0, 0), 在 [2,3,6,7] 中取一个, path = []
i = 0:path = [2],递归 backtracking([2,3,6,7], 7, 0, 0),回溯,path = [] ...
i = 3:path = [7],递归 backtracking([2,3,6,7], 7, 0, 3),回溯,path = []
// 深度2: 例: backtracking([2,3,6,7], 7, 0, 0), 在 [2,3,6,7] 中取一个, path = [2]
i = 0:path = [2,2],递归 backtracking([2,3,6,7], 7, 0, 0),回溯,path = [2]
i = 1:path = [2,3],递归 backtracking([2,3,6,7], 7, 0, 1),回溯,path = [2]
i = 2:不满足 2 + 6 <= 7, 停止遍历(剪枝)
// 深度3: 例: backtracking([2,3,6,7], 7, 0, 0), 在 [2,3,6,7] 中取一个, path = [2,2]
i = 0:path = [2,2,2],递归 backtracking([2,3,6,7], 7, 0, 0),回溯,path = [2,2]
i = 1:path = [2,2,3],递归 backtracking([2,3,6,7], 7, 0, 1,回溯,path = [2,2]
i = 2:不满足 4 + 6 <= 7, 停止遍历(剪枝)
// 深度n: 以此类推
https://www.programmercarl.com/0039.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C.html