Open youngyangyang04 opened 5 months ago
回溯最直观的例子应该是走出迷宫
private void backtracking(int n, int k, int start) {
if (path.size() == k) {
paths.add(new ArrayList<>(path)); // 存放结果
return;
}
for (int i = start; i <= n - (k - path.size()) + 1; i++) {
path.add(i); // 1. 处理节点
backtracking(n, k, i + 1); // 2. 递归
path.remove(path.size() - 1); // 3. 回溯
}
}
// backtracking(4, 2, 1): 在 1、2、3 中取一个数 (path = [])
i = 1:path = [1],递归 backtracking(4, 2, 2),回溯,path = []
i = 2:path = [2],递归 backtracking(4, 2, 3),回溯,path = []
i = 3:path = [3],递归 backtracking(4, 2, 4),回溯,path = []
// backtracking(4, 2, 2): 在 2、3、4 中取一个数 (path = [1])
i = 2:path = [1,2],长度为 2,加入到 paths 中,回溯,path = [1]
i = 3:path = [1,3],长度为 2,加入到 paths 中,回溯,path = [1]
i = 4:path = [1,4],长度为 2,加入到 paths 中,回溯,path = [1]
// backtracking(4, 2, 3): 在 3、4 中取一个数 (path = [2])
i = 3:path = [2,3],长度为 2,加入到 paths 中,回溯,path = [2]
i = 4:path = [2,4],长度为 2,加入到 paths 中,回溯,path = [2]
// backtracking(4, 2, 4): 在 4 中取一个数 (path = [3])
i = 4:path = [3,4],长度为 2,加入到 paths 中,回溯,path = [3]
https://www.programmercarl.com/0077.%E7%BB%84%E5%90%88.html