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