面试刷题必会：回溯法详解（python代码模板，学会了秒杀回溯题）

迈不过友情╰ 2022-11-06 01:57 11阅读 0赞

## 回溯法 ##

> **「回溯法」实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就「回溯」返回，尝试别的路径。**

回溯法是一种算法思想，而递归是一种编程方法，回溯法可以用递归来实现。

回溯法的整体思路是：搜索每一条路，每次回溯是对具体的一条路径而言的。对当前搜索路径下的的未探索区域进行搜索，则可能有两种情况：

当前未搜索区域满足结束条件，则保存当前路径并退出当前搜索；  
当前未搜索区域需要继续搜索，则遍历当前所有可能的选择：如果该选择符合要求，则把当前选择加入当前的搜索路径中，并继续搜索新的未探索区域。  
上面说的未搜索区域是指搜索某条路径时的未搜索区域，并不是全局的未搜索区域。

**回溯法搜所有可行解的模板一般是这样的：**

res = []
    path = []
    
    def backtrack(未探索区域, res, path):
        if 未探索区域满足结束条件:
            res.add(path) # 深度拷贝
            return
        for 选择 in 未探索区域当前可能的选择:
            if 当前选择符合要求:
                path.add(当前选择)
                backtrack(新的未探索区域, res, path)
                path.pop()

**解释：**

backtrack 的含义是：未探索区域中到达结束条件的所有可能路径，path 变量是保存的是一条路径，res 变量保存的是所有搜索到的路径。所以当「未探索区域满足结束条件」时，需要把 path 放到结果 res 中。

path.pop() 是啥意思呢？它是编程实现上的一个要求，即我们从始至终只用了一个变量 path，所以当对 path 增加一个选择并 backtrack 之后，需要清除当前的选择，防止影响其他路径的搜索。

**复杂度：**  
时间复杂度：O(2 ^ N)  
空间复杂度：O(2 ^ N)

**例题：**

> 1、力扣刷题 131.分割回文串（回溯经典题，直接套模板）：  
> [https://blog.csdn.net/weixin\_44414948/article/details/114490837][https_blog.csdn.net_weixin_44414948_article_details_114490837]  
> 2、力扣刷题：17.电话号码的字母组合（回溯模板题）：  
> [https://blog.csdn.net/weixin\_44414948/article/details/114549813][https_blog.csdn.net_weixin_44414948_article_details_114549813]  
> 3、力扣刷题：22.括号生成（回溯模板题）：  
> [https://blog.csdn.net/weixin\_44414948/article/details/114551416][https_blog.csdn.net_weixin_44414948_article_details_114551416]

> 参考来源：[https://leetcode-cn.com/problems/palindrome-partitioning/solution/hui-su-fa-si-lu-yu-mo-ban-by-fuxuemingzh-azhz/][https_leetcode-cn.com_problems_palindrome-partitioning_solution_hui-su-fa-si-lu-yu-mo-ban-by-fuxuemingzh-azhz]

[https_blog.csdn.net_weixin_44414948_article_details_114490837]: https://blog.csdn.net/weixin_44414948/article/details/114490837
[https_blog.csdn.net_weixin_44414948_article_details_114549813]: https://blog.csdn.net/weixin_44414948/article/details/114549813
[https_blog.csdn.net_weixin_44414948_article_details_114551416]: https://blog.csdn.net/weixin_44414948/article/details/114551416
[https_leetcode-cn.com_problems_palindrome-partitioning_solution_hui-su-fa-si-lu-yu-mo-ban-by-fuxuemingzh-azhz]: https://leetcode-cn.com/problems/palindrome-partitioning/solution/hui-su-fa-si-lu-yu-mo-ban-by-fuxuemingzh-azhz/