Day21回溯算法專題做到第三篇。前兩篇我們已經(jīng)把組合類問題的套路磨得很熟了——從最基本的77題組合開始到組合總和I/II再到電話號(hào)碼的字母組合backtracking函數(shù)的骨架已經(jīng)刻進(jìn)肌肉記憶了。但到了part03難度開始上一個(gè)真正的臺(tái)階這一篇的核心不再是組合而是子集和分割兩個(gè)新場(chǎng)景。說實(shí)在的我從組合跳到子集問題的時(shí)候第一反應(yīng)是這倆不是一回事嗎。但真動(dòng)手寫代碼才發(fā)現(xiàn)子集問題和組合問題的思維模型有本質(zhì)區(qū)別——組合關(guān)注的是選滿k個(gè)就收手子集關(guān)注的是每個(gè)節(jié)點(diǎn)都要記錄而分割問題更是把選擇徹底抽象成了切割線的位置。這篇文章就把part03里最核心的幾道題串起來講清楚三個(gè)場(chǎng)景各自的門道以及它們背后是怎么共用同一套回溯模板的。1. 子集問題從收集葉子到收集每個(gè)節(jié)點(diǎn)的思維切換子集問題在LeetCode上對(duì)應(yīng)的是78題題目描述很簡(jiǎn)單給一個(gè)不包含重復(fù)元素的整數(shù)數(shù)組返回所有可能的子集。比如[1,2,3]要輸出[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]。如果你已經(jīng)寫過組合總和那一系列題目第一眼看上去會(huì)覺得子集和組合的代碼幾乎一樣都在遞歸里用startIndex控制下一層起點(diǎn)都是選了當(dāng)前元素然后往深層走。但有一個(gè)極其關(guān)鍵的差異——收集結(jié)果的位置。組合問題的經(jīng)典寫法是void backtracking(vectorint candidates, int target, int sum, int startIndex) { if (sum target) { result.push_back(path); return; } // ... for 循環(huán)選擇 }只有在滿足終止條件時(shí)才把path塞進(jìn)result。說白了組合問題的結(jié)果是收集樹的葉子節(jié)點(diǎn)中間過程產(chǎn)生的所有中間狀態(tài)都不是最終答案。子集問題恰恰相反整棵樹的每一個(gè)節(jié)點(diǎn)不管深度多少不管下面還會(huì)不會(huì)繼續(xù)遞歸都是合法子集。所以收集動(dòng)作必須放在進(jìn)入遞歸前的代碼里且不能放在終止條件之后被return擋住。class Solution { private: vectorvectorint result; vectorint path; void backtracking(vectorint nums, int startIndex) { result.push_back(path); // 每個(gè)節(jié)點(diǎn)都收集 if (startIndex nums.size()) { return; } for (int i startIndex; i nums.size(); i) { path.push_back(nums[i]); backtracking(nums, i 1); path.pop_back(); } } public: vectorvectorint subsets(vectorint nums) { backtracking(nums, 0); return result; } };這段代碼里最容易寫錯(cuò)的點(diǎn)就是把這行result.push_back(path);放到if (startIndex nums.size())里面。如果放進(jìn)去結(jié)果會(huì)是當(dāng)遞歸走到startIndex越過數(shù)組末尾時(shí)才記錄一次path——那樣收集到的就只是完整走到最后的路徑中間那些諸如[1]、[2]這種淺層子集全都會(huì)丟。還有個(gè)細(xì)節(jié)值得說一下這里遞歸函數(shù)沒有顯式的剪枝操作因?yàn)樽蛹瘑栴}需要遍歷所有分支剪枝反而會(huì)漏答案。這一點(diǎn)和組合總和那道題里sum target就return的思路完全不同新手最容易慣性代入組合題的剪枝邏輯。從復(fù)雜度上算一下nums長度為n時(shí)子集總數(shù)是2^n每個(gè)子集復(fù)制進(jìn)result的成本是O(n)所以總時(shí)間復(fù)雜度是O(n * 2^n)空間復(fù)雜度O(n)主要花在遞歸棧上。這也是回溯類題目里典型的兩倍增長復(fù)雜度看到2^n心里要有個(gè)譜。實(shí)際刷題經(jīng)驗(yàn)告訴我第一次做子集題與其硬背模板不如在紙上把這棵遞歸樹畫出來。[1,2,3]的整棵樹畫一遍你就知道為什么收集語句必須在遞歸之前了——因?yàn)槊總€(gè)有path值的狀態(tài)都是答案。2. 去重的真正難點(diǎn)樹層去重與樹枝去重為什么不能混為一談子集問題做完基礎(chǔ)版緊跟著就是90題子集II輸入數(shù)組變成可能包含重復(fù)元素。比如[1,2,2]你要輸出的結(jié)果不能含有重復(fù)子集。這題本質(zhì)考察的是回溯中的去重邏輯和組合總和II里那套去重思路一脈相承但因?yàn)樗自谧蛹瘑栴}上又容易讓人掉進(jìn)另一個(gè)坑。先說結(jié)論需要在同一層同一輪for循環(huán)內(nèi)跳過重復(fù)元素這就是樹層去重。實(shí)現(xiàn)上兩種主流寫法寫法一用used數(shù)組記錄狀態(tài)class Solution { private: vectorvectorint result; vectorint path; void backtracking(vectorint nums, int startIndex, vectorbool used) { result.push_back(path); for (int i startIndex; i nums.size(); i) { if (i 0 nums[i] nums[i - 1] used[i - 1] false) { continue; } used[i] true; path.push_back(nums[i]); backtracking(nums, i 1, used); path.pop_back(); used[i] false; } } public: vectorvectorint subsetsWithDup(vectorint nums) { sort(nums.begin(), nums.end()); vectorbool used(nums.size(), false); backtracking(nums, 0, used); return result; } };寫法二直接用startIndex跳過void backtracking(vectorint nums, int startIndex) { result.push_back(path); for (int i startIndex; i nums.size(); i) { if (i startIndex nums[i] nums[i - 1]) { continue; } path.push_back(nums[i]); backtracking(nums, i 1); path.pop_back(); } }先說一個(gè)很多人忽略的前提不管用哪種寫法第一步必須先排序。used數(shù)組去重的核心是依賴相鄰相等的檢測(cè)不排序的話相等的元素在數(shù)組里不相鄰nums[i] nums[i-1]根本判斷不到。這是90題和40題里最容易踩的暗坑。再說說used[i - 1] false這個(gè)條件到底是什么意思很多博客講到這里都含糊其辭。我換個(gè)理解方式在一個(gè)分支的遞歸深度上縱向如果used[i-1] true說明當(dāng)前正在這個(gè)元素的分支內(nèi)部繼續(xù)擴(kuò)展這是正常的、允許的。比如數(shù)組[1,2,2]先選了第一個(gè)2然后遞歸進(jìn)入第二個(gè)2此時(shí)前一個(gè)2的used為true路徑[2,2]是合法子集不能跳過。如果used[i - 1] false說明前一個(gè)相同的元素剛在上一層被撤銷了選擇而當(dāng)前這層又遇到了同樣的值。這代表兩個(gè)路徑在處理同一層時(shí)元素值相同繼續(xù)走就會(huì)和上一次for循環(huán)的結(jié)果完全重復(fù)所以直接跳過。我在part02做組合總和II時(shí)也用過這個(gè)used數(shù)組但當(dāng)時(shí)只記住了遇到相同就continue沒理解深層的橫向/縱向區(qū)別結(jié)果一到子集II這種需要每一層都收集結(jié)果的場(chǎng)景就懵了。這里我推薦一個(gè)調(diào)試方法在backtracking函數(shù)里把used數(shù)組當(dāng)前狀態(tài)和startIndex打印出來配合i的值逐層看很快就能看出什么時(shí)候used[i-1]為false什么時(shí)候?yàn)閠rue。肉眼看得見比空想要清楚得多?；氐絻煞N寫法的取舍上。寫法二用i startIndex是我個(gè)人現(xiàn)在更常用的因?yàn)樗恍枰~外維護(hù)used數(shù)組代碼更短但它的理解門檻稍微高一點(diǎn)——你必須透徹地知道i startIndex意味著在同一層循環(huán)里已經(jīng)處理過這個(gè)值了這本質(zhì)上就是樹層去重。寫法一更直白配合used[i-1] false這個(gè)條件可以做到和寫法二完全相同的效果但它需要你給backtracking函數(shù)多傳一個(gè)參數(shù)。刷題階段我建議先把寫法一練熟面試手撕的時(shí)候用寫法二會(huì)顯得更干凈。這里有個(gè)重要的區(qū)別要提醒兩個(gè)寫法在同一個(gè)位置的具體行為上并不完全等價(jià)。比如數(shù)組[1,2,2]寫法一是基于全數(shù)組全局的used狀態(tài)去判斷而寫法二是基于當(dāng)前for循環(huán)的起點(diǎn)去判斷。大多數(shù)情況下二者結(jié)果一樣但如果你的遞歸里還有其他進(jìn)出棧的不對(duì)稱邏輯可能會(huì)導(dǎo)致細(xì)節(jié)差異。穩(wěn)妥起見如果你已經(jīng)能熟練理解used數(shù)組就一直用used數(shù)組理解不了就一直用i startIndex別兩種混著寫混著寫最容易出bug。3. 分割問題的本質(zhì)把切割線當(dāng)成組合中的選擇節(jié)點(diǎn)如果說子集問題是在組合的模板上換了個(gè)收集時(shí)機(jī)那分割問題就是把組合問題的抽象方式整個(gè)換了一遍——這也是part03里我認(rèn)為思維跨度最大的一步。典型題目是131題分割回文串給定一個(gè)字符串返回所有可能的分割方案要求每個(gè)子串都是回文串。比如aab結(jié)果要是[[a,a,b],[aa,b]]。我第一次看到這題陷入了困惑前面刷的組合題都是在一個(gè)一維數(shù)組上做選擇這題給的是一個(gè)字符串怎么選選的是什么答案是你選的不是字符而是切割點(diǎn)的位置。在字符串中切割點(diǎn)的位置本質(zhì)上與組合中startIndex之后選哪個(gè)元素是一樣的——每一層遞歸startIndex就是上一刀切完之后的起點(diǎn)而for循環(huán)里i的每一次迭代就代表在i這個(gè)位置切下一刀。代碼長這樣class Solution { private: vectorvectorstring result; vectorstring path; bool isPalindrome(const string s, int start, int end) { while (start end) { if (s[start] ! s[end]) return false; start; end--; } return true; } void backtracking(const string s, int startIndex) { if (startIndex s.size()) { result.push_back(path); return; } for (int i startIndex; i s.size(); i) { if (isPalindrome(s, startIndex, i)) { string str s.substr(startIndex, i - startIndex 1); path.push_back(str); backtracking(s, i 1); path.pop_back(); } } } public: vectorvectorstring partition(string s) { backtracking(s, 0); return result; } };這里最值得琢磨的是if (isPalindrome(s, startIndex, i))這個(gè)判斷放的位置。它不是在終止條件里做校驗(yàn)而是在進(jìn)入下一層遞歸之前就做準(zhǔn)入檢查。這和組合問題里不滿足條件就不選的邏輯一樣——組合里可以提前判斷sum是否超過target分割里則是提前判斷當(dāng)前準(zhǔn)備切的這段子串是不是回文。如果不做這個(gè)判斷硬把所有切法都試一遍到葉子節(jié)點(diǎn)才統(tǒng)一檢查那遞歸樹的規(guī)模會(huì)急劇膨脹做aab這種小字符串不明顯但字符串一長性能差距立刻爆發(fā)出來。用生活化的類比來說startIndex就是你手上的刀下一次要落下的位置i是你這次打算切到的位置。一次切割得到一段字符串然后遞歸的下一層從i1重新開始。整個(gè)遞歸樹展示的其實(shí)是所有可能的切法組合。我實(shí)際測(cè)試下來這種先判斷再遞歸的剪枝方式在處理長回文串時(shí)比全切出來再做判斷快非常多。比如對(duì)aaaaa...這種全是同一個(gè)字符的極端例子剪枝與否差距是指數(shù)級(jí)別的。我還試過把isPalindrome改成在遞歸外部預(yù)先算出一個(gè)布爾矩陣dp[i][j]表示s[i..j]是否回文然后用O(1)查表代替雙指針判斷。對(duì)超長字符串測(cè)試場(chǎng)景確實(shí)有優(yōu)化效果但代碼復(fù)雜度上去了不太利于面試時(shí)快速講清楚日常刷題或面試用雙指針的isPalindrome就夠了。4. 復(fù)原IP地址多個(gè)前置校驗(yàn)疊加在回溯框架上分割問題里還有一道比分割回文串更綜合的題93題復(fù)原IP地址。給定一個(gè)只含數(shù)字的字符串比如25525511135還原出所有合法的IP地址組合。這道題也是用backtracking做切割但相比分割回文串多了三個(gè)客觀條件的約束第一IP地址必須恰好四段第二每一段必須是一個(gè)合法的數(shù)字0~255之間且不能有前導(dǎo)零第三每一段不能為空。三個(gè)約束疊加就特別考驗(yàn)?zāi)惆雅袛鄺l件嵌進(jìn)遞歸框架的能力。核心實(shí)現(xiàn)如下class Solution { private: vectorstring result; bool isValid(const string s, int start, int end) { if (start end) return false; if (s[start] 0 start ! end) return false; int num 0; for (int i start; i end; i) { if (s[i] 0 || s[i] 9) return false; num num * 10 (s[i] - 0); if (num 255) return false; } return true; } void backtracking(string s, int startIndex, int pointNum) { if (pointNum 3) { if (isValid(s, startIndex, s.size() - 1)) { result.push_back(s); } return; } for (int i startIndex; i s.size(); i) { if (isValid(s, startIndex, i)) { s.insert(s.begin() i 1, .); pointNum 1; backtracking(s, i 2, pointNum); pointNum - 1; s.erase(s.begin() i 1); } } } public: vectorstring restoreIpAddresses(string s) { if (s.size() 4 || s.size() 12) return result; backtracking(s, 0, 0); return result; } };這道題有至少四個(gè)細(xì)節(jié)值得單獨(dú)拿出來講。第一終止條件的設(shè)定。這里用pointNum 3而不是startIndex s.size()作為遞歸出口。因?yàn)镮P地址恰好四段只要插了三個(gè)點(diǎn)就已經(jīng)把字符串分成四段了。剩下要做的事情就只剩一件事驗(yàn)證最后一段是否合法。這個(gè)設(shè)計(jì)比切完所有字符再檢查要優(yōu)雅得多也省去了很多無效遞歸。第二字符串的增刪操作。insert和erase是std::string里的操作時(shí)間復(fù)雜度O(n)但因?yàn)樽址L度最多也就12個(gè)字符這個(gè)成本可以忽略不計(jì)。需要注意的是插入一個(gè)點(diǎn)之后下一次遞歸的起點(diǎn)從i1變成了i2——因?yàn)橐^.這個(gè)字符。這里特別容易寫錯(cuò)成i1一錯(cuò)就會(huì)反復(fù)檢查到插入的句點(diǎn)。第三for循環(huán)里的合法性判斷剪枝。如果s[startIndex..i]這一段本身就不是有效數(shù)字比如超過了255那就不用再往i后面試了。注意這個(gè)地方可以加個(gè)小優(yōu)化如果剩余字符數(shù)量比需要的還多可以直接break或continue因?yàn)楫?dāng)前段已經(jīng)不可能劃分出合法IP了。第四主函數(shù)里的一行防御代碼if (s.size() 4 || s.size() 12) return result;。字符串長度小于4不可能分成四段大于12則必然有一段超過三位數(shù)。這個(gè)前置判斷在LeetCode上能幫你省掉一大撥邊界用例的遞歸開銷屬于典型的入口處先堵住明顯不合法輸入的思路。我在刷這道題時(shí)踩過的最蠢的坑是忘了判斷前導(dǎo)零。比如010010這種字符串0.10.0.10算不算合法其實(shí)每一段的0是合法的單獨(dú)的0但01之類的前導(dǎo)零就不合法。我一開始的isValid只判斷了數(shù)字是否大于255結(jié)果把01.0.0.1這種也當(dāng)成了合法IP直接提交就是Wrong Answer。所以判斷前導(dǎo)零的邏輯必須單獨(dú)寫if (s[start] 0 start ! end) return false;——意思是只有長度大于1且以0開頭的段才非法單獨(dú)一段0完全合法。5. 回溯part01到part03的一條主線模式識(shí)別的方法論做完part03這三類題之后我最大的感受是回溯算法看似每個(gè)題的代碼都差不多但真正區(qū)分難度的是你能不能快速識(shí)別出這道題到底屬于哪一種抽象模型。我到part03才算把這條主線理順了。先放一個(gè)我從三天題目里總結(jié)出來的對(duì)照表問題類型抽象選擇的對(duì)象終止條件結(jié)果收集位置典型題目組合從一組數(shù)里選k個(gè)path.size() k葉子節(jié)點(diǎn)77, 216, 39, 40子集從一組數(shù)里選任意個(gè)startIndex越界每個(gè)節(jié)點(diǎn)78, 90分割在一維結(jié)構(gòu)上選切割點(diǎn)startIndex走到末尾葉子節(jié)點(diǎn)131, 93這張表不是死記硬背用的而是當(dāng)你拿到一道新題時(shí)用來做模式匹配的。拿到題目先做三連問答案是不是若干個(gè)元素的組合如果是看有沒有數(shù)量限制有就套組合模板。答案是不是所有子集/所有不重復(fù)組合如果是把收集語句提到遞歸之前。答案是不是把一個(gè)字符串/序列劃分成若干合法片段如果是把for循環(huán)里的i理解成切割點(diǎn)用startIndex表示上一次切割結(jié)束的位置。這套方法論其實(shí)是從代碼隨想錄回溯專題的編排思路里延伸出來的part01打基礎(chǔ)組合、組合總和part02練細(xì)節(jié)去重、剪枝part03就是逼你把抽象模型靈活切換。子集問題的收集所有節(jié)點(diǎn)和分割問題的把切割點(diǎn)當(dāng)作選擇本質(zhì)都是對(duì)同一棵遞歸樹的不同解讀方式。還有一點(diǎn)值得反復(fù)體會(huì)回溯算法寫的次數(shù)多了你會(huì)發(fā)現(xiàn)模板本身幾乎不變變的是三樣?xùn)|西——result里最終裝的是什么、path里累積的是什么、以及每次遞歸的終止條件是什么。如果你能做到看到一個(gè)題就快速把這三點(diǎn)分別說出來回溯類題目就基本通關(guān)了。我這幾天的實(shí)際經(jīng)驗(yàn)是不要著急多刷題每做完一道題就打開代碼用熒光筆在紙上標(biāo)出收集位置剪枝位置終止條件這三處對(duì)比不同題目之間的差異。等積累到五六個(gè)題之后你會(huì)發(fā)現(xiàn)原本模糊的模式識(shí)別能力會(huì)變得非常清晰。Day21的part03說到底練的不只是三道題的解法而是建立這種看題先歸類的思維習(xí)慣。