问题	贪心选择	状态表示	关键技巧
摆动序列	只保留方向转折点	`prev_diff`	符号判断 + 跳过平台
过河问题	每次最优送走最慢两人	排序后索引	两种策略比较 + 分治思想

贪心成功的关键：问题具有最优子结构，且局部最优能导向全局最优。同时，正确设计状态与策略是避免错误的核心。

本次内容

📌 回溯法的定义：

回溯法是一种通过深度优先搜索（DFS） 遍历解空间树（通常为隐式树）的算法技术。它在搜索过程中逐步构建候选解，并在发现当前部分解无法扩展为合法解时，立即放弃（剪枝） 并回退（回溯） 到上一步，尝试其他选择。

换句话说，回溯法是一种“试错 + 撤销”的策略：

尝试某种选择 →
若后续无法达成目标 →
撤销该选择 →
尝试下一个可能。

🔑 回溯法的核心要素：

解的表示：将问题的解表示为一个向量（如 [x₁, x₂, ..., xₙ]），每个分量在特定阶段从候选集中选择。
约束条件：用于判断当前部分解是否可能扩展为完整合法解。
目标函数（可选）：在优化问题中用于评估解的优劣（回溯通常用于求所有解或一个可行解，而非最优解；若求最优，常需与分支限界结合）。
递归与状态恢复：通过递归探索选择，回溯时需恢复状态（如撤销对数组、集合、棋盘的修改）。

⏱️ 时间复杂度特点：

最坏情况下需遍历整个解空间，复杂度通常为指数级（如 O(kⁿ)，k 为每步平均选择数）。
但通过剪枝（Pruning）（即提前终止无效分支），在实践中可显著提升效率。

✅ 与贪心、动态规划的区别：

方法	决策方式	是否可撤销	适用场景
贪心	局部最优，不可撤销	❌	具有贪心选择性质的问题
动态规划	全局最优，记忆化	❌	有重叠子问题 + 最优子结构
回溯法	尝试所有可能路径	✅	解空间有限、需穷举+剪枝

📝 小结：

回溯法 = 递归 + 选择 + 约束检查 + 回溯（状态撤销）
它是“聪明的穷举”——通过提前剪枝避免无效搜索，是解决离散组合问题的有力工具。

真题演练：

📌 回溯法精要总结

回溯法 = 递归 + 选择 + 撤销
用于系统性地枚举所有满足约束的解，适用于组合、排列、搜索类问题。

♛ N皇后问题

目标：在 N×N 棋盘放 N 个皇后，互不攻击（不同行、列、对角线）。
策略：
- 逐行放置（天然避免行冲突）；
- 对每列检查：列、主对角线、副对角线是否已有皇后；
- 递归尝试 → 成功则记录解 → 回溯（恢复 '.'）。
关键：checkPosition 实现冲突检测，chessBoard[row][col] = 'Q' 后递归，返回后重置。

📱 电话号码的字母组合

目标：给数字串（如 "23"），输出所有对应字母组合（如 ["ad","ae",...]）。
策略：
- 预置数字→字母映射；
- 递归逐位选择字母，构建路径；
- 到达末尾则加入结果；
- 回溯时 pop() 恢复路径。
特点：无冲突约束，纯组合生成，结构清晰。

🔁 回溯通用模板（精简版）

def backtrack(path, index):
    if 满足终止条件:
        result.append(path[:])
        return
    for choice in 选择列表:
        path.append(choice)      # 做选择
        backtrack(path, index+1) # 递归
        path.pop()               # 撤销选择

✅ 核心要点

适用场景：需要枚举所有可行解（如排列、组合、布局）；
效率关键：尽早剪枝（如 N 皇后的冲突检查）；
空间开销：递归栈 + 路径存储，一般为 O(解深度)；
与贪心/DP区别：回溯穷举可行解，不追求“最优”而是“全部”或“存在”。

回溯法是解决离散组合搜索问题的基石，掌握其模板可应对大量经典题目。