回溯算法（Backtracking） 回溯算法是一种通过逐步构建候选解并在确定当前部分解无法得到有效完整解时放弃该部分解（回溯）的算法框架。它通常用于解决组合优化、约束满足等问题，如八皇后、数独、全排列等。 核心思想与步骤 回溯法可视为对解空间的深度优先搜索，其核心在于“尝试-回溯”的循环： 选择 ：在当前步骤，从可选集合中选取一个候选加入部分解。 约束检查 ：判断当前部分解是否满足问题的约束条件。若违反，则放弃该分支（剪枝）。 目标检查 ：若当前部分解已构成一个完整解，则记录该解。 递归扩展 ：若部分解尚未完成，则基于当前状态递归进入下一选择步骤。 回溯 ：撤销最后一步选择，返回上一状态，尝试其他候选。 示例：全排列问题 以数组 [1, 2, 3] 的全排列为例，需生成所有不重复的排列顺序。 步骤分解 初始化 ：创建一个空列表 path 存储当前部分解，一个集合 used 记录已使用的元素（避免重复选择）。 递归函数定义 ： 参数：当前路径 path 、已使用标记 used 、原始数组 nums 、结果集 result 。 终止条件：当 path 长度等于 nums 长度时，说明已得到一个排列，将其加入 result 。 遍历候选元素 ： 遍历 nums 中每个元素，若该元素未被使用（ used[i] 为 false ），则： 选择 ：将元素加入 path ，标记 used[i] = true 。 递归 ：进入下一层决策（处理剩余未使用元素）。 回溯 ：从 path 中移除该元素，标记 used[i] = false ，以尝试其他候选。 执行过程示意 （简化版）： 第一层：选1 → path = [1] ，递归进入第二层。 第二层：选2 → path = [1, 2] ，递归进入第三层。 第三层：选3 → path = [1, 2, 3] （完整解），记录后回溯到第二层。 第二层回溯：撤销2，改选3 → path = [1, 3] ，递归进入第三层选2，得到 [1, 3, 2] 。 第一层回溯：撤销1，改选2 → 重复类似过程，生成以2开头的排列。 继续直至所有分支遍历完毕。 关键优化：剪枝 在递归前检查约束条件，避免无效搜索。例如在八皇后问题中，若当前皇后位置与已有皇后冲突，则直接跳过该分支。 复杂度分析 时间复杂度通常与状态空间大小相关，最坏情况下为 O(分支数^深度)。全排列问题为 O(n !)。 空间复杂度主要取决于递归栈深度，一般为 O(递归深度)。 应用场景 组合问题（如子集、组合求和） 排列问题（如全排列、N皇后） 路径搜索（如迷宫问题、图的哈密顿路径） 回溯法通过系统性地尝试所有可能分支，并利用剪枝减少无效计算，是解决NP难问题的有效策略。