回溯演算法#

回溯演算法（Backtracking）是一種透過試錯來尋找問題解的演算法策略，本質上是帶有剪枝功能的深度優先搜尋（DFS）。

本章內容#

• 回溯演算法原理：核心概念與程式碼模板
• 剪枝技術：優化搜尋效率的關鍵策略
• 經典問題：N 皇后、數獨、括號生成

核心思維#

回溯法的精髓：嘗試 → 檢查 → 遞迴 → 失敗則撤銷

這是對解空間樹的深度優先走訪，遇到死路就「回溯」到上一步嘗試其他可能。

回溯三要素#

1. 選擇列表：當前可做的選擇
2. 路徑：已經做出的選擇
3. 結束條件：到達決策樹底層的條件

與其他演算法的關係#

回溯法是暴力搜尋的優化版本，透過剪枝提前排除無效分支。