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++) {
if (i > start && nums[i] == nums[i - 1]) continue; // 去重
sum += nums[i];
path.add(nums[i]);
backtracking(nums, target, sum, i + 1);
sum -= nums[i];
path.remove(path.size() - 1);
}
}
// 深度1: backtracking([1,1,2,5,6,7,10], 8, 0, 0), path = []
i = 0:path = [1],递归 backtracking([1,1,2,5,6,7,10], 8, 0, 1),回溯,path = []
i = 1:满足 1 == 1, 继续遍历(剪枝) ...
i = 6:path = [10],递归 backtracking([1,1,2,5,6,7,10], 8, 0, 7),回溯,path = []
// 深度2: 例: backtracking([1,1,2,5,6,7,10], 8, 0, 1), path = [1]
i = 1:path = [1,1],递归 backtracking([1,1,2,5,6,7,10], 8, 0, 2),回溯,path = [1] ...
i = 5:path = [1,7],递归 backtracking([1,1,2,5,6,7,10], 8, 0, 8),回溯,path = [1]
i = 6:不满足 1 + 10 <= 8, 停止遍历(剪枝)
// 深度3: 例: backtracking([1,1,2,5,6,7,10], 8, 0, 2), path = [1,1]
i = 2:path = [1,1,2],递归 backtracking([1,1,2,5,6,7,10], 8, 0, 3),回溯,path = [1,1] ...
i = 5:不满足 2 + 7 <= 8, 停止遍历(剪枝)
// 深度n: 以此类推
https://www.programmercarl.com/0040.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CII.html