回溯法简介

回溯法的算法思维能帮助我们解决很多复杂的问题，通过递归 + 回溯可以帮助我们将问题拆分成更简单的子问题，使得我们有能力在碰到一些复杂的问题的时候去解决。

本节的知识点很大程度上参考了 一篇总结带你彻底搞透回溯算法！ ，总结了各类回溯的问题。

什么是回溯（Backtrack）

**回溯法（backtrack）**是优先搜索的一种特殊情况，又称为试探法。回溯法的核心是回溯，是记录节点状态的深度搜索。

[修改当前节点状态]→[递归子节点]
[修改当前节点状态]→[递归子节点]→[回改当前节点状态] # 回溯法加入了节点状态的修改

搜索效率

回溯法就是纯暴力的穷举搜索算法，时间复杂度一般为 $O(N!)$

虽然回溯法是暴力循环的一种，但是它能解决一些多重嵌套解决不了的代码。

回溯法遍历的过程就是决策树遍历的过程，为了提升效率，一般配上树的剪枝。

模板

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

适用问题

回溯法的经典问题有：

$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)

参考教程

1. 一篇总结带你彻底搞透回溯算法！

2. 回溯法