回溯算法要点总结

本文主要是介绍回溯算法要点总结，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

本质
暴力搜索、枚举

使用场景
1.组合问题:N个数里面按一定规律找出k个数的组合
2.排列问题:N个数按一定规则全排序，有几种排列方式
3.切割问题:一个字符串按一定规则有几种切割方式
4.子集问题:一个N个数的集合里有多少符合条件的子集
5.棋盘问题:N皇后,解数独等等

要点

1. 回溯算法都可以抽象成一个树。
   1.1 递归纵向遍历树，递归层数=树高
   1.2 for循环横向遍历树，循环次数等于每层的节点数
2. 回溯与递归总是成对出现的,所以递归三部曲也适用回溯算法
3. 递归控制for循环嵌套的数量

优化
通过剪枝提高效率
在40题中发现一个新思路:先进行排序，排序的目的是为了剪枝
在求和问题中，排序之后加剪枝是常见的套路！
如果输入有重复元素且排序后的结果与排序前的结果没有差别，可以看了先排序。

模板

void backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

组合问题

什么适合可以使用startIndex来控制for循环的起始位置？

• 多个集合取组合，各个集合之间互不影响,就不用startIndex
• 一个集合取组合，就需要startIndex

切割问题

切割问题其实类似组合问题

排列问题

• 每层都是从0开始搜索
• 需要visited数组记录path路径里放了哪些元素

这篇关于回溯算法要点总结的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！