選一步、走下去、走不通就撤回。用 DFS 系統化地試遍所有可能,還會提早剪枝。
選一步 —— 從目前能做的選項挑一個,做下去(記錄這個選擇)。
往下遞迴 —— 在「做了這個選擇」的新狀態下,繼續解剩下的。
撤銷(backtrack) —— 若這條路失敗,把剛剛的選擇收回,試下一個選項。
跟純 DFS 差在哪 —— 就是多了「撤銷」那一步,把狀態還原,才能乾淨地試下一條路。
暴力法會試「所有」組合 —— 例如 N 皇后有 nⁿ 種擺法,天文數字。
回溯會提早放棄 —— 只要目前的部分擺法已經違規(兩皇后互攻),就不再往下,整條分支砍掉。
這叫剪枝(pruning) —— 越早發現不可行、砍掉越多,實際跑起來越快。
好的剪枝是效率關鍵 —— 同一個問題,剪得好可以差好幾個數量級(數獨、N 皇后都靠它秒解)。
試一片,不合就拿起來換下一片(撤銷),合了才繼續拼旁邊。
每道門試一把,開了往前走;走到死路就退回上一道門換路線。
填一個數,矛盾就擦掉重填(撤銷),一格一格逼近答案。
在 4×4 棋盤放 4 個皇后,讓它們互不攻擊(同行、同列、同對角線都算)。回溯一列一列試:能放就放(紫色放下、綠色已放),琥珀是被現有皇后攻擊、不能放的格子;整列都放不了就回溯收回上一個。按「下一步」。
回溯的招牌題:全排列、子集、組合、N 皇后、括號生成、數獨、字母組合、單字搜尋,最後給通用模板。
❌ 忘了撤銷 —— 選了沒收回,狀態會髒掉、影響其他分支,答案全錯。
❌ 收集解時沒複製 —— result.append(path) 存的是同一個 list 的參照,之後會被改掉;要 path[:] 或 list(path)。
❌ 沒有剪枝 —— 能提早判斷不可行卻不剪,會慢到跑不完。
❌ 組合 / 子集沒用 start 去重 —— 要用 start 只往後選,不然會冒出重複或變成排列。
O(n!)、子集 O(2ⁿ) 都指數級,那「剪枝」到底幫了什麼忙?(提示:數獨若不剪枝要試幾種?)把答案打到對話裡,我幫你對。