---

🚀 回溯算法通關秘籍：像打怪一樣刷題！

各位同學，今天咱們聊聊 回溯算法（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 循環里遞歸

常見題型 = 排列、組合、子集、棋盤

面試必考，刷熟就無敵！

---

🌟 建議收藏 + 敲一遍代碼，不然很快就忘了。回溯題就像武俠里的招式，光看口訣沒用，得實戰才會「內功心法」。