算法设计范式
回溯法
回溯法是一种系统化的搜索办法：用来遍历「构建某样东西的所有方式」——一种摆放、一种排列、一条路径——它每次只扩展部分解一个选择，一旦发现这条路绝无可能成立就立即放弃，并撤销最后一个选择去尝试别的。脑海里的画面是一边探迷宫、一边拖着一根线：你沿走廊往前推进，一撞上死胡同就退回上一个岔口、换一扇门去试。关键在于，你后退时会把最后一步抹掉——这个「撤销」正是 backtrack（回溯）一词的字面含义。
三个动作构成了循环：选择（做出下一个决定）、探索（递归地继续扩展解）、撤销选择（撤回这个决定，让下一个并列选择从干净的起点开始）。回溯之所以远胜过盲目的暴力枚举，靠的是剪枝：在每一个部分步骤上你都检查约束，若部分解已经违反约束，就把整条分支砍掉、连它底下的子孙都不去探索。在 N 皇后问题里，你逐列放置皇后，一旦某列的皇后会攻击到已放好的某个，就立即放弃这一列——省下了它底下那一大片子树。
回溯法是生成全排列或全子集、解数独和填字游戏、求解 N 皇后谜题、以及一般约束满足问题背后的引擎。它诚实的代价在最坏情况下是指数级的——毕竟它探索的是一棵可能极其庞大的搜索树——所以它是否实用，完全取决于约束让你剪枝剪得有多狠。好的剪枝，正是「毫秒内返回」与「永远不返回」之间的分水岭。
void permute(vector<int>& a, int k) {
if (k == a.size()) { record(a); return; } // a full arrangement
for (int i = k; i < a.size(); ++i) {
swap(a[k], a[i]); // choose
permute(a, k + 1); // explore
swap(a[k], a[i]); // un-choose (backtrack)
}
}「交换再换回」的写法，正是「选择／探索／撤销」循环的缩影。
回溯法本质上是在「部分解构成的树」上做深度优先搜索，外加一步——回退时撤销每个选择。没有剪枝，它就退化成穷举式的暴力枚举；正是那些让你及早放弃注定无果分支的约束检查，赋予了它力量。
又称
另见