演算法設計範式
回溯法
回溯法是一種系統化的搜尋辦法：用來走訪「構建某樣東西的所有方式」——一種擺放、一種排列、一條路徑——它每次只擴展部分解一個選擇，一旦發現這條路絕無可能成立就立即放棄，並撤銷最後一個選擇去嘗試別的。腦海裡的畫面是一邊探迷宮、一邊拖著一根線：你沿走廊往前推進，一撞上死胡同就退回上一個岔口、換一扇門去試。關鍵在於，你後退時會把最後一步抹掉——這個「撤銷」正是 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)
}
}「交換再換回」的寫法，正是「選擇／探索／撤銷」迴圈的縮影。
回溯法本質上是在「部分解構成的樹」上做深度優先搜尋，外加一步——回退時撤銷每個選擇。沒有剪枝，它就退化成窮舉式的暴力枚舉；正是那些讓你及早放棄注定無果分支的約束檢查，賦予了它力量。
又稱
另見