主题切换
回溯
一、回溯算法的核心流程
回溯算法是一种基于深度优先搜索（DFS）的暴力枚举算法，通过构建解空间树，在搜索过程中对不满足条件的分支进行剪枝，从而找到所有符合条件的解。其核心流程可分为以下七步：
二、第一步：确定状态
状态是回溯算法的核心，代表当前递归过程中的所有关键信息。
- 包含当前处理的位置、已选择的元素、限制条件的使用情况等
- 状态需要完整描述当前递归的进度，确保后续步骤可以正确执行
三、第二步：非法状态
在递归过程中，首先需要判断当前状态是否为非法状态：
- 若当前状态不满足题目限制条件（如越界、重复选择、不符合业务规则），直接返回
- 提前过滤非法状态，避免无效的递归调用
四、第三步：更新状态
当状态合法时，进入递归处理逻辑：
- 将当前选择的元素加入解路径
- 更新状态变量（如标记已使用元素、修改计数等）
- 记录当前状态，为后续递归做准备
五、第四步：结束状态
当递归到达结束条件时，保存当前解并返回：
- 结束条件通常为解的长度达到目标值、所有元素处理完毕等
- 保存当前路径到结果集合中，完成一次有效解的收集
六、第五步：状态转移
在当前状态下，遍历所有可能的下一步选择：
- 枚举所有合法的候选元素（如未被使用的数字、相邻的节点等）
- 对每个候选元素递归调用回溯函数，继续深度搜索
七、第六步：还原状态
递归返回后，需要撤销当前状态的修改，恢复到进入递归前的状态：
- 将当前选择的元素从解路径中移除
- 恢复状态变量（如取消标记已使用元素、恢复计数等）
- 确保后续分支的状态不受当前分支的影响
八、第七步：状态剪枝
在递归过程中，对明显无法得到有效解的分支进行剪枝：
- 提前过滤重复分支（如排序后跳过相同元素）
- 对不满足条件的分支直接返回，减少不必要的递归调用
- 大幅降低时间复杂度，避免暴力枚举所有情况
九、面试相关问题
问：回溯算法的核心思想是什么？答： 回溯算法的核心思想是暴力枚举所有可能的解，通过深度优先搜索构建解空间树，并在搜索过程中对不满足条件的分支进行剪枝，从而找到所有符合条件的解。它通过“试错”的方式逐步构建解，当发现当前路径无法得到有效解时，回溯到上一步，尝试其他可能的选择。
问：回溯算法的七步流程分别是什么？答： 回溯算法的七步流程为：
- 第一步：确定状态，明确递归过程中的关键信息；
- 第二步：过滤非法状态，避免无效递归；
- 第三步：更新状态，记录当前选择；
- 第四步：判断结束状态，保存有效解；
- 第五步：状态转移，枚举所有可能的下一步选择；
- 第六步：还原状态，撤销当前选择的影响；
- 第七步：状态剪枝，优化递归效率。
问：回溯算法中“还原状态”的作用是什么？答： 还原状态是回溯算法的关键步骤，它的作用是撤销当前递归分支对状态的修改，恢复到进入递归前的状态，确保后续分支的搜索不受当前分支的影响。例如，当处理完一个元素后，需要将其从解路径中移除、取消标记已使用状态，这样下一个候选元素才能正确使用该状态变量。
问：回溯算法的时间复杂度为什么很高？如何优化？答： 回溯算法的时间复杂度通常为指数级（如O(2ⁿ)、O(n!)），因为它本质上是暴力枚举所有可能的解。优化方式主要是通过状态剪枝：
- 提前过滤重复分支，避免重复计算；
- 对明显无法得到有效解的分支直接返回；
- 排序后跳过相同元素，减少重复搜索；
- 利用题目条件限制，提前判断分支是否可能得到有效解。