回溯法简介
回溯法的算法思维能帮助我们解决很多复杂的问题,通过递归 + 回溯可以帮助我们将问题拆分成更简单的子问题,使得我们有能力在碰到一些复杂的问题的时候去解决。
本节的知识点很大程度上参考了 一篇总结带你彻底搞透回溯算法! (opens new window) ,总结了各类回溯的问题。
# 什么是回溯(Backtrack)
**回溯法(backtrack)**是优先搜索的一种特殊情况,又称为试探法。回溯法的核心是回溯,是记录节点状态的深度搜索。
[修改当前节点状态]→[递归子节点]
[修改当前节点状态]→[递归子节点]→[回改当前节点状态] # 回溯法加入了节点状态的修改
1
2
2
# 搜索效率
回溯法就是纯暴力的穷举搜索算法,时间复杂度一般为 $O(N!)$
虽然回溯法是暴力循环的一种,但是它能解决一些多重嵌套解决不了的代码。
回溯法遍历的过程就是决策树遍历的过程,为了提升效率,一般配上树的剪枝。
# 模板
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
处理节点;
backtracking(路径,选择列表); // 递归
回溯,撤销处理结果
}
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 适用问题
回溯法的经典问题有:
$A_n^k$
问题分类 | LeetCode题目问题 |
---|---|
排列问题:$A_n^k$ | 46. 全排列(Medium) 47. 全排列 II(Medium) |
组合问题: $C_n^k$ | 77. 组合(Medium) 216. 组合总和 III(Medium) 39. 组合总和 40. 组合总和 II 17. 电话号码的字母组合(Medium) |
切割问题 | 131. 分割回文串(Medium) 93. 复原IP |
子集问题 | 78. 子集(Medium) 90. 子集 II(Medium) 491. 递增子序列 |
棋盘问题 | 51. N皇后(hard) 37. 解数独(Hard) |
# 参考教程
编辑 (opens new window)
上次更新: 2022/10/25, 02:40:54