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