Open youngyangyang04 opened 3 months ago
private void backtracking(int[] nums, int start) {
paths.add(new ArrayList<>(path));
for (int i = start; i < nums.length; i++) {
path.add(nums[i]);
backtracking(nums, i + 1);
path.remove(path.size() - 1);
}
}
// 深度1: backtracking([1,2,3], 0), path = []
i = 0:path = [1],递归 backtracking([1,2,3], 1),加入 paths。回溯,path = []
i = 1:path = [2],递归 backtracking([1,2,3], 2),加入 paths。回溯,path = []
i = 2:path = [3],递归 backtracking([1,2,3], 3),加入 paths。回溯,path = []
// 深度2: 例: backtracking([1,2,3], 1), path = [1]
i = 1:path = [1,2],递归 backtracking([1,2,3], 2),加入 paths。回溯,path = [1]
i = 2:path = [1,3],递归 backtracking([1,2,3], 3),加入 paths。回溯,path = [1]
// 深度3: 例: backtracking([1,2,3], 2), path = [1,2]
i = 2:path = [1,2,3],递归 backtracking([1,2,3], 3),加入 paths。回溯,path = [1,2]
说白了就是二叉树的前序遍历呗 这个回溯法的模本
https://www.programmercarl.com/0078.%E5%AD%90%E9%9B%86.html