回溯算法這四個字我在剛學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法》那會兒就聽過但真正把它放在心上是在刷算法題時遇到八皇后和一堆排列組合問題。你可能會發(fā)現(xiàn)不少題目表面上是“暴力枚舉算法”可一旦數(shù)據(jù)量上來純暴力直接卡死?；厮菟惴ň褪悄莻€“看起來暴力、實際上有章法”的系統(tǒng)化搜索方法它一路走到黑走不通就回頭換一條路再試。很多算法工程師面試和藍橋杯算法題目里回溯都是高頻考點它看起來簡單但真要寫好剪枝、處理好撤銷狀態(tài)沒有點實操經(jīng)驗還真容易翻車。在動手寫代碼之前不妨先把回溯算法的形象在腦子里立起來。這個算法不是某個花哨的數(shù)據(jù)結(jié)構(gòu)也不是高深莫測的數(shù)學(xué)技巧它本質(zhì)上是一種非常樸素的窮舉思路把所有可能的解都嘗試一遍但嘗試的過程不是無腦遍歷而是像在一棵決策樹上做深度優(yōu)先遍歷。哪里走不通就退回來換一條分支這也就是“回溯”兩個字的意思。1. 回溯算法是什么先別急著寫碼1.1 用一個生活中的例子講透核心思想想象你在玩一個迷宮游戲。你走進一個岔路口選擇一條路向前探索如果前方是死胡同你不會站在原地發(fā)呆而是會退回上一個岔路口換另一條路繼續(xù)嘗試。這個過程就是回溯嘗試、判斷失敗、回退、嘗試新的可能。把這個過程抽象成程序邏輯每一步都包含幾件事做選擇當(dāng)前可以選哪些方向或哪些值。判斷約束這個選擇是否滿足題目的限制條件。遞歸推進如果約束通過就進入下一層繼續(xù)嘗試。撤銷選擇如果當(dāng)前選擇導(dǎo)致后續(xù)無法完成目標(biāo)需要回到選擇之前的狀態(tài)才能嘗試下一條路。這看起來和“遞歸”是親兄弟確實如此?；厮菟惴ㄒ话愣紩眠f歸來實現(xiàn)因為遞歸天然具備“?！钡奶匦院瘮?shù)調(diào)用的返回機制恰好提供了回退的能力。提示如果你對遞歸還不太熟建議先把遞歸的調(diào)用棧畫出來再來看回溯理解上會順很多。1.2 回溯和暴力枚舉到底差在哪很多人會把回溯和暴力枚舉混為一談因為本質(zhì)上它們都在窮舉。但兩者的區(qū)別非常關(guān)鍵暴力枚舉是先把所有可能的組合全部生成出來再去逐個檢查回溯則是在生成的過程中就不斷淘汰不滿足條件的部分能省下大量無效計算。舉一個具體的例子。假設(shè)要生成一個長度為 3 的三位數(shù)字組合每一位可以從 0 到 9 中選擇且要求數(shù)字不能重復(fù)。純暴力枚舉的做法是先把 10 * 10 * 10 1000 個組合全部生成出來然后逐一過濾掉有重復(fù)的回溯的做法則是第一位選完之后第二位只會選擇還沒用過的數(shù)字第三位同理直接避免生成重復(fù)組合。雖然最終結(jié)果一樣但回溯過程砍掉了很多不必要的分支效率差異在數(shù)據(jù)量增大后會非常明顯。所以回溯算法可以理解為“帶條件的暴力枚舉”而這個“條件”就是題目里的限制。當(dāng)你把限制條件很好地用到搜索過程中就形成了剪枝。剪枝是回溯算法里最值得研究的動作也是把“暴力”變得“優(yōu)雅”的核心。2. 核心技術(shù)拆解模板、剪枝與撤銷2.1 一套通用模板幾乎所有回溯題都能套我見過很多初學(xué)者學(xué)回溯時喜歡背題但說實話與其背題不如背模板。回溯算法的骨架是高度統(tǒng)一的基本可以歸納為這樣一段偽代碼邏輯def backtrack(路徑, 選擇列表): if 滿足結(jié)束條件: 記錄結(jié)果 return for 選擇 in 選擇列表: 做選擇 backtrack(路徑, 新的選擇列表) 撤銷選擇把這個模板換成實際的 Python 代碼以“求一個數(shù)組的所有子集”為例大概是這個樣子def subsets(nums): res [] path [] def backtrack(start): res.append(path[:]) # 記錄當(dāng)前路徑 for i in range(start, len(nums)): path.append(nums[i]) # 做選擇 backtrack(i 1) # 遞歸進入下一層 path.pop() # 撤銷選擇 backtrack(0) return res這里有一個很容易踩的坑在記錄結(jié)果時為什么要寫成res.append(path[:])而不是res.append(path)因為path是一個列表對象遞歸過程中它會被不斷修改。如果直接把這個列表對象放進去后續(xù)所有path.pop()操作都會改變這個對象最終你會發(fā)現(xiàn)結(jié)果列表里全是同一個不斷變化的列表。注意Python 里列表是引用類型保存結(jié)果時一定要用切片path[:]或copy()拷貝一份。2.2 剪枝的藝術(shù)越早切斷收益越大剪枝的本質(zhì)就是在遞歸搜索的過程中提前判斷某些分支不可能產(chǎn)生有效解從而直接跳過不再進入那一層遞歸。剪枝做得好不好很大程度上決定了回溯算法在實際問題中能不能跑得動。剪枝通常有兩種可行性剪枝當(dāng)前選擇的組合已經(jīng)不滿足題目條件比如總和超過目標(biāo)值再往下發(fā)展也不可能回頭直接剪掉。最優(yōu)性剪枝當(dāng)前路徑的代價已經(jīng)超過已知的最優(yōu)解即使繼續(xù)搜索也不可能獲得更好結(jié)果直接剪掉。我拿一個“組合總和”問題舉例。題目要求從給定數(shù)組中選出若干個數(shù)使它們的和等于目標(biāo)值。如果當(dāng)前累加的和已經(jīng)超過目標(biāo)值那么無論后續(xù)再選什么總和只會更大于是立刻停止這條分支的遞歸。這就是可行性剪枝。所以我會建議拿到一個回溯題先不要急著寫代碼。先把遞推過程中哪些情況是“永遠不可能有效”的理清楚再決定剪枝條件。剪枝寫得好很多本來會超時的題目唰一下就跑過去了。2.3 撤銷選擇為什么比“做選擇”還重要“撤銷選擇”看起來只是path.pop()這么一行代碼但很多人就是會忘記寫。忘記撤銷的直接后果是同一層的狀態(tài)被污染結(jié)果或分支錯亂。你會看到明明該換一個選擇了path 里卻還殘留著上一次選擇的數(shù)據(jù)。你可以把回溯理解成一場“時光倒流”的游戲遞歸進入下一層之前是一個平行世界從下一層返回之后當(dāng)前世界必須保持進入之前的樣子不然所有分支都會互相影響。這個“回到過去”的操作就是撤銷選擇。再補充一點經(jīng)驗常見的選擇狀態(tài)不只有路徑數(shù)組還包括布爾標(biāo)記數(shù)組used、哈希表、甚至某些全局變量。在寫遞歸函數(shù)的時候要明確哪些變量是“狀態(tài)變量”需要在進入遞歸前修改、從遞歸返回后恢復(fù)。只要有一個狀態(tài)變量沒有還原排查起來就會非常痛苦。3. 經(jīng)典問題實操從排列組合到八皇后3.1 全排列、組合、子集這幾類問題各有各的坑排列、組合、子集是回溯算法最經(jīng)典的初階題型也是后續(xù)很多復(fù)雜題目的基礎(chǔ)。它們之間的區(qū)別在于“選擇列表”和控制順序的方式。全排列的代碼通常會引入一個used數(shù)組用來標(biāo)記某個元素是否已經(jīng)在當(dāng)前路徑中使用過def permute(nums): res, path, used [], [], [False] * len(nums) def backtrack(): if len(path) len(nums): res.append(path[:]) return for i in range(len(nums)): if used[i]: continue # 同一個枝丫上已經(jīng)用過的元素跳過 used[i] True path.append(nums[i]) backtrack() path.pop() used[i] False backtrack() return res組合和子集不一樣的點在于它們需要刻意避免重復(fù)組合。比如[1, 2]和[2, 1]在組合里是同一種情況。處理方式是用一個start參數(shù)限制下一層只能從當(dāng)前索引之后開始選也就是上一節(jié)模板里的做法。這種“順序限制”是解決組合類問題的核心思想。還有一個必考的變體數(shù)組里有重復(fù)元素要去重。比如[1, 1, 2]的全排列結(jié)果不能出現(xiàn)兩組[1, 1, 2]。我試過很多種寫法最穩(wěn)妥的方法是對數(shù)組先排序然后在循環(huán)里加一個條件if i 0 and nums[i] nums[i - 1] and not used[i - 1]: continue這個條件的含義是如果當(dāng)前元素和前一個元素相同且前一個元素在上一個分支回退時已經(jīng)被釋放說明當(dāng)前分支會生成與前一個分支重復(fù)的結(jié)果直接跳過即可。3.2 八皇后問題的完整實現(xiàn)與流程拆解八皇后問題幾乎是回溯算法課程里的“標(biāo)配”。題目要求在一個 8x8 的棋盤上放置 8 個皇后讓它們彼此之間不能在同一行、同一列或同一對角線上互相攻擊。我第一次寫八皇后時遇到的最大困惑是如何表示棋盤狀態(tài)這里有一個很巧妙的方法用一維數(shù)組queen[row] col來表示第row行的皇后放在第col列。因為每一行只能放一個皇后所以不需要完整的二維棋盤。判斷是否可以放置的關(guān)鍵代碼在于兩點列沖突col與已放置皇后的某一列相同。對角線沖突行差和列差的絕對值相等。完整代碼可以這樣寫def solve_n_queens(n): res [] queen [-1] * n def is_valid(row, col): for r in range(row): if queen[r] col or abs(queen[r] - col) row - r: return False return True def backtrack(row): if row n: board [. * c Q . * (n - c - 1) for c in queen] res.append(board) return for col in range(n): if is_valid(row, col): queen[row] col backtrack(row 1) queen[row] -1 backtrack(0) return res從流程上拆解從第 0 行開始嘗試第 0 列到第 7 列。遇到一個不沖突的位置就放下皇后進入第 1 行。如果第 1 行所有位置都沖突函數(shù)自然結(jié)束回到第 0 行并嘗試下一列。一直遞歸到第 8 行說明 8 個皇后都放好了記錄結(jié)果。最后把路徑一路回退繼續(xù)找其他可能解。這個流程畫出來就是一張 8 叉樹形狀的搜索圖每一步的搜索空間大約呈現(xiàn)指數(shù)級最后的可行解只有 92 個但搜索過程中訪問的分支遠不止這些。這也是為什么你需要在代碼里認真實現(xiàn)剪枝判斷。3.3 從八皇后到數(shù)獨回溯問題的常見變體八皇后學(xué)會之后你可以順手挑戰(zhàn)更多經(jīng)典變形題比如數(shù)獨求解、迷宮路徑、圖的著色、括號生成、單詞搜索等。這些題表面形式不同但本質(zhì)都是搜索一組滿足約束條件的解。拿數(shù)獨來說每一格嘗試 1 到 9 的數(shù)字不滿足行、列、宮約束就換一個數(shù)字到了無解的位置就回退上一層重新選擇。思路很清楚難點在于狀態(tài)表示和剪枝優(yōu)化可以像八皇后一樣用三個二維布爾數(shù)組分別標(biāo)記行、列和宮是否已使用某個數(shù)字。這樣判斷合法性可以從 O(9) 降到 O(1)在搜索速度上的提升非?？捎^。這類問題的共同點是解空間非常大而且存在明顯的約束條件。你只要把“約束條件”翻譯成剪枝邏輯再用統(tǒng)一的回溯模板去套基本思路就不會跑偏。4. 復(fù)雜度分析與優(yōu)化技巧別被“指數(shù)級”嚇到4.1 回溯算法的時間復(fù)雜度怎么算回溯算法的時間復(fù)雜度沒有統(tǒng)一的公式因為搜索空間取決于問題的解空間大小。但是有一個非常實用的分析方法畫出選擇樹算一算樹的節(jié)點總數(shù)。以全排列為例輸入長度為n第一層有n個選擇第二層每個分支有n-1個選擇第三層有n-2個選擇總節(jié)點數(shù)就是n n*(n-1) n*(n-1)*(n-2) ... n!也就是說全排列的時間復(fù)雜度穩(wěn)定在 O(n!)。八皇后問題類似它的搜索空間上界是 n 的階乘級別但由于對角線約束實際訪問的分支會少很多?？臻g復(fù)雜度則主要是遞歸調(diào)用棧的深度通常是 O(n)加上臨時路徑或狀態(tài)數(shù)組的 O(n)仍然可認為是線性級別。這也是回溯算法的一個優(yōu)點它可能跑得慢但不會像動態(tài)規(guī)劃那樣占用大量額外空間主要代價在時間里。如果需要向算法工程師面試官清晰地說明復(fù)雜度我建議表達成“最壞情況下是 O(指數(shù)級)但因為剪枝平均表現(xiàn)往往好很多”并在紙上推導(dǎo)一遍選擇樹的節(jié)點數(shù)量就很有說服力。4.2 幾個我用下來效率提升明顯的優(yōu)化手段先說排序剪枝如果題目允許提前排序比如求組合總和先把候選數(shù)組從小到大排好序一旦當(dāng)前累加值超過目標(biāo)值就可以直接跳出循環(huán)因為后面所有的數(shù)只會更大。這種優(yōu)化能讓代碼提速一個檔次。再說位運算優(yōu)化在處理棋盤類或者狀態(tài)壓縮類回溯題時可以用一個整數(shù)的二進制位來表示某行某列是否被占用。例如直接把已經(jīng)占用的列、主對角線、副對角線用位掩碼表示每次只需要幾次位運算就能判斷合法性比遍歷數(shù)組快很多。我在處理 N 皇后進階題時用這種方法代碼雖然難讀一點但性能確實立竿見影。還有一個容易忽略的技巧是“選擇順序優(yōu)化”。在搜索開始前盡量把更可能觸發(fā)約束的元素放在前面或者把分支更少的位置先嘗試。這樣能讓搜索更快地逼近有效解同時也能更快地觸發(fā)剪枝條件。提示回溯算法基本不可能做到多項式時間復(fù)雜度所以優(yōu)化目標(biāo)是“少走彎路”而不是徹底去掉指數(shù)級上界。5. 常見問題與排查從藍橋杯到面試都在踩的坑5.1 看一下這幾個典型問題你中招過幾個我復(fù)盤了自己和身邊人對回溯算法的調(diào)試經(jīng)歷很多問題非常集中列成一張速查表會非常直觀常見癥狀可能原因排查建議結(jié)果全是一樣的空列表忘寫path[:]拷貝或保存后繼續(xù)修改同一對象保存結(jié)果前復(fù)制一份結(jié)果數(shù)量過少或分支缺失剪枝條件寫錯了把有效分支也剪掉了給剪枝條件打印日志看看出現(xiàn)重復(fù)結(jié)果沒有對相同元素去重或者沒有限制組合順序先排序再在循環(huán)內(nèi)跳過相同元素遞歸死循環(huán)或棧溢出結(jié)束條件不完整或剪枝條件漏掉了某些情況檢查遞歸函數(shù)里的出口條件狀態(tài)被后續(xù)分支污染某個標(biāo)記數(shù)組或變量沒有在遞歸返回后恢復(fù)逐項檢查所有“做選擇”時修改的狀態(tài)其中“狀態(tài)污染”是新手最容易忽略、也最難排查的一類問題。我見過一個同學(xué)做了選擇之后忘了把used[i]改回False結(jié)果明明應(yīng)該是 6 種排列的全排列硬生生只輸出了 3 種。這個 bug 肉眼看不出來必須用調(diào)試器走一遍才能發(fā)現(xiàn)問題。5.2 我用過的幾個排查與打印技巧回溯代碼的調(diào)試第一步永遠是“小規(guī)模測試”。把n改到 3 或者 4運行一下用非常小的輸入跑一遍全流程。如果小規(guī)模輸出都不對就不要急著去調(diào)大輸入先在紙上把小規(guī)模的狀態(tài)樹畫出來然后和代碼的打印結(jié)果對照。第二個技巧是把backtrack函數(shù)開頭加上這樣一句調(diào)試日志def backtrack(row, queen): print(進入行, row, 當(dāng)前布局, queen)在關(guān)鍵分支里多打印幾行就能清晰地看到“何時進入選擇”“何時剪枝返回”。我實際調(diào)試時經(jīng)常用這種方式效果比兩眼一抹黑地盯著代碼好很多。在確定邏輯沒問題后再把打印語句刪掉。第三個核心經(jīng)驗是實在找不到 bug就忽略整體輸出只追蹤某個特定的結(jié)果分支。比如八皇后問題假設(shè)正確解有 92 個某個解找不到了可以固定前兩個皇后的位置讓它只搜索部分空間再用樣例輸出對照人工枚舉的結(jié)果。這種鎖定分支的方式能大幅縮小排查范圍。5.3 在藍橋杯和算法面試中回溯題目怎么拿分藍橋杯算法題目里回溯題往往不是最難的但它經(jīng)常作為暴力枚舉的替代解法出現(xiàn)特別是當(dāng)數(shù)據(jù)范圍不大時寫回溯加剪枝通常能拿到不錯的分?jǐn)?shù)。我比賽時的一個策略是如果題目看著像搜索題第一反應(yīng)先考慮回溯寫一個“能跑通但可能稍慢”的版本保底再去想有沒有更優(yōu)的動態(tài)規(guī)劃或數(shù)學(xué)解法。算法工程師面試中回溯題更看重的是思路是否清晰、邊界條件是否考慮得全面。面試官通常不會要求你把 8 皇后寫成位運算優(yōu)化后的版本但會很在意你能不能解釋為什么用used數(shù)組、為什么剪枝條件寫在這里、復(fù)雜度的上界是多少。只要把模板和復(fù)雜度分析講清楚面試這關(guān)基本就穩(wěn)了。不過我還是要提醒一句回溯算法不等于萬金油。如果題目有明顯的重疊子問題比如很多計數(shù)類問題優(yōu)先考慮動態(tài)規(guī)劃如果問題具備“最優(yōu)子結(jié)構(gòu)”貪心往往更高效?；厮莺线m的場景是“需要顯式地枚舉所有解或判斷是否存在合法解”這個分寸把握住了才不會出現(xiàn)解題方向跑偏的情況。6. 最后分享一點我的實操體會從第一次寫全排列各種報錯到后來能靠畫狀態(tài)樹十分鐘定位問題最大的感受是回溯算法真的不復(fù)雜復(fù)雜的地方在于“耐心”兩個字。你對狀態(tài)空間梳理得越清楚寫出來的代碼就越是水到渠成你對模板越熟悉考試和面試時就越能從容應(yīng)對。最后再分享一個小技巧做回溯題時一定要先用筆在紙上把樣例的搜索樹從頭到尾畫一遍哪怕是最小規(guī)模的那么簡單。我覺得光靠腦子空想非常容易漏掉關(guān)鍵的剪枝條件或狀態(tài)恢復(fù)而紙上推演一遍以后再轉(zhuǎn)化成代碼就會順暢很多。把這棵樹畫熟了很多東西就變成了一種肌肉記憶往后遇到類似的搜索題你也能在五分鐘內(nèi)給出一個可堪一用的回溯方案。