---

🚀 回溯算法通关秘籍：像打怪一样刷题！

各位同学，今天咱们聊聊 回溯算法（Backtracking）。它听起来玄乎，但其实就是 “暴力搜索 + 剪枝” 的优雅版。
打个比方：回溯就是在迷宫里探险，一条路走不通，咱就原路返回（Backtrack），换条路继续走，直到走到出口。

---

🎮 核心思想：DFS + 状态撤销

回溯的套路其实就三句话：

1. 选择：尝试在当前状态下做一个选择（比如选某个数字、某个字符）。

2. 递归：继续往下走，探索下一个决策点。

3. 撤销：如果发现走不通，就撤销刚才的选择，换个选项再试。

可以理解为：

“换工作 → 不合适 → 离职（撤销） → 入职新公司 → 继续尝试” 🤣

---

📝 模板代码（黄金三板斧）

void backtrack(路径 path, 选择列表 choices) {
if (满足结束条件) {
结果集.add(path);
return;
}

for (选择 in choices) {if (不合法选择) continue; // 剪枝做选择(path, 选择);      // 前进backtrack(path, 更新后的choices);撤销选择(path, 选择);    // 回溯
}

}

是不是很像玩游戏时的「尝试技能 → 如果凉了 → 回档 → 换个技能」？

---

🧩 经典题型（刷题就靠它！）

1. 排列问题

题目：给你数组 [1,2,3]，输出所有排列。

特点：路径长度 = 数组长度，不允许重复选。

2. 组合问题

题目：在 [1,2,3,4] 中选出所有长度为 2 的组合。

特点：顺序无关，强调“选还是不选”。

3. 子集问题

题目：输出 [1,2,3] 的所有子集。

特点：走到每一层都能记录一次结果。

4. 棋盘类问题（八皇后、数独）

特点：大量剪枝，考验写代码时的自我控制力。

---

✂️ 剪枝：少走弯路的秘诀

有时候题目数据量大，如果不剪枝，时间复杂度会爆炸。
举个栗子 🌰：

组合总和问题：如果当前和已经 > target，就不用再继续下去了。

N皇后问题：如果当前列、斜线有冲突，就直接跳过。

剪枝就像打游戏时的「副本指南」：提前告诉你哪些路别走，省时省力。

---

😂 诙谐小口诀（方便记忆）

回溯三件套：选、递归、撤销！
没路就掉头，结果全带走。
剪枝要果断，不然爆显存。
面试官常问，写熟你最稳！

---

🎯 总结

回溯 = DFS + 状态撤销

套路 = for 循环里递归

常见题型 = 排列、组合、子集、棋盘

面试必考，刷熟就无敌！

---

🌟 建议收藏 + 敲一遍代码，不然很快就忘了。回溯题就像武侠里的招式，光看口诀没用，得实战才会「内功心法」。