回溯算法的總結(jié)心得

回溯算法的總結(jié)心得第1篇回溯算法的總結(jié)心得第1篇這么說(shuō)是不是有點(diǎn)抽象？

來(lái)來(lái)來(lái)，我就用輸入:[1,1,1]來(lái)舉一個(gè)例子。

樹(shù)層上去重(used[i-1]==false)，的樹(shù)形結(jié)構(gòu)如下：

樹(shù)枝上去重（used[i-1]==true）的樹(shù)型結(jié)構(gòu)如下：

大家應(yīng)該很清晰的看到，樹(shù)層上對(duì)前一位去重非常徹底，效率很高，樹(shù)枝上對(duì)前一位去重雖然最后可以得到答案，但是做了很多無(wú)用搜索。

這道題其實(shí)還是用了我們之前講過(guò)的去重思路，但有意思的是，去重的代碼中，這么寫(xiě)：

和這么寫(xiě)：

都是可以的，這也是很多同學(xué)做這道題目困惑的地方，知道used[i-1]==false也行而used[i-1]==true也行，但是就想不明白為啥。

所以我通過(guò)舉[1,1,1]的例子，把這兩個(gè)去重的邏輯分別抽象成樹(shù)形結(jié)構(gòu)，大家可以一目了然：為什么兩種寫(xiě)法都可以以及哪一種效率更高！

這里可能大家又有疑惑，既然used[i-1]==false也行而used[i-1]==true也行，那為什么還要寫(xiě)這個(gè)條件呢？

直接這樣寫(xiě)不就完事了？

其實(shí)并不行，一定要加上used[i-1]==false或者used[i-1]==true，因?yàn)閡sed[i-1]要一直是true或者一直是false才可以，而不是一會(huì)是true一會(huì)又是false。所以這個(gè)條件要寫(xiě)上。

是不是豁然開(kāi)朗了！！

13.重新安排行程

給你一份航線列表tickets，其中tickets[i]=[fromi,toi]表示飛機(jī)出發(fā)和降落的機(jī)場(chǎng)地點(diǎn)。請(qǐng)你對(duì)該行程進(jìn)行重新規(guī)劃排序。

所有這些機(jī)票都屬于一個(gè)從JFK（肯尼迪國(guó)際機(jī)場(chǎng)）出發(fā)的先生，所以該行程必須從JFK開(kāi)始。如果存在多種有效的行程，請(qǐng)你按字典排序返回最小的行程組合。

假定所有機(jī)票至少存在一種合理的行程。且所有的機(jī)票必須都用一次且只能用一次。

回溯算法的總結(jié)心得第2篇回溯法的性能如何呢，這?要和?家說(shuō)清楚了，雖然回溯法很難，很不好理解，但是回溯法并不是什么?效的算法。因?yàn)榛厮莸谋举|(zhì)是窮舉，窮舉所有可能，然后選出我們想要的答案，如果想讓回溯法?效?些，可以加?些剪枝的操作，但也改不了回溯法就是窮舉的本質(zhì)。那么既然回溯法并不?效為什么還要?它呢？因?yàn)闆](méi)得選，?些問(wèn)題能暴?搜出來(lái)就不錯(cuò)了，撐死了再剪枝?下，還沒(méi)有更?效的解法。此時(shí)?家應(yīng)該好奇了，都什么問(wèn)題，只能暴?搜索

組合問(wèn)題：N個(gè)數(shù)??按?定規(guī)則找出k個(gè)數(shù)的集合切割問(wèn)題：?個(gè)字符串按?定規(guī)則有?種切割?式?集問(wèn)題：?個(gè)N個(gè)數(shù)的集合?有多少符合條件的?集排列問(wèn)題：N個(gè)數(shù)按?定規(guī)則全排列，有?種排列?式棋盤問(wèn)題：N皇后，解數(shù)獨(dú)等等

例如：{1,2}和{2,1}在組合上，就是?個(gè)集合，因?yàn)椴粡?qiáng)調(diào)順序，?要是排列的話，{1,2}和{2,1}就是兩個(gè)集合了。記住組合?序，排列有序，就可以了。

題目：

給定兩個(gè)整數(shù)n和k，返回1…n中所有可能的k個(gè)數(shù)的組合。

?例:輸?:n=4,k=2輸出:[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],]思路：直接的解法當(dāng)然是使?for循環(huán)，例如?例中k為2，很容易想到?兩個(gè)for循環(huán)，這樣就可以輸出和?例中?樣的結(jié)果。代碼如下：

輸?：n=100,k=3那么就三層for循環(huán)，代碼如下：

如果n為100，k為50呢，那就50層for循環(huán)，是不是開(kāi)始窒息。此時(shí)就會(huì)發(fā)現(xiàn)雖然想暴?搜索，但是?for循環(huán)嵌套連暴?都寫(xiě)不出來(lái)！

如果for循環(huán)選擇的起始位置之后的元素個(gè)數(shù)已經(jīng)不?我們需要的元素個(gè)數(shù)了，那么就沒(méi)有必要搜索了。

接下來(lái)看?下優(yōu)化過(guò)程如下：

為什么有個(gè)+1呢，因?yàn)榘ㄆ鹗嘉恢?，我們要?個(gè)左閉的集合。舉個(gè)例?，n=4，k=3，?前已經(jīng)選取的元素為0（為0），n-(k-0)+1即4-(3-0)+1=2。從2開(kāi)始搜索都是合理的，可以是組合[2,3,4]

回溯算法的總結(jié)心得第3篇在回溯算法:電話號(hào)碼的字母組合中，開(kāi)始用多個(gè)集合來(lái)求組合，還是熟悉的模板題目，但是有一些細(xì)節(jié)。例如這里for循環(huán)，可不像是在回溯算法:求組合問(wèn)題!和回溯算法:求組合總和!中從startIndex開(kāi)始遍歷的。因?yàn)楸绢}每一個(gè)數(shù)字代表的是不同集合，也就是求不同集合之間的組合，而回溯算法:求組合問(wèn)題!和回溯算法:求組合總和!都是是求同一個(gè)集合中的組合!

6、對(duì)于切割問(wèn)題，切割回文串那道題目，難點(diǎn)在于以下方面：

7、對(duì)于求子集的問(wèn)題，在子集問(wèn)題一中，在樹(shù)形結(jié)構(gòu)中子集問(wèn)題是要收集所有節(jié)點(diǎn)的結(jié)果，而組合問(wèn)題是收集葉子節(jié)點(diǎn)的結(jié)果。在子集問(wèn)題二中，需要對(duì)子集進(jìn)行去重，邏輯與以前一樣的，用一個(gè)used數(shù)組里進(jìn)行標(biāo)記。在遞增子序列中，不能對(duì)原序列進(jìn)行排序，也可以使用set針對(duì)同一父節(jié)點(diǎn)本層去重。

8、對(duì)于求排列的問(wèn)題。排列是有序的，也就是說(shuō)[1,2]和[2,1]是兩個(gè)集合，這和之前分析的子集以及組合所不同的地方。

排列問(wèn)題也要去重了，在回溯算法:排列問(wèn)題(二)心中又一次強(qiáng)調(diào)了_樹(shù)層去重_和”樹(shù)枝去重”。

使用set去重的版本相對(duì)于used數(shù)組的版本效率都要低很多，主要是因?yàn)槌绦蜻\(yùn)行的時(shí)候?qū)nordered_set頻繁的insert,unordered_set需要做哈希映射（也就是把key通過(guò)hashfunction映射為唯一的哈希值）相對(duì)費(fèi)時(shí)間，而且insert的時(shí)候其底層的符號(hào)表也要做相應(yīng)的擴(kuò)充，也是費(fèi)時(shí)的。而使用used數(shù)組在時(shí)間復(fù)雜度上幾乎沒(méi)有額外負(fù)擔(dān)!，使用set去重，不僅時(shí)間復(fù)雜度高了，空間復(fù)雜度也高了，組合，子集，排列問(wèn)題的空間復(fù)雜度都是O(n)，但如果使用set去重，空間復(fù)雜度就變成了O(n^2)，因?yàn)槊恳粚舆f歸都有一個(gè)set集合，系統(tǒng)?？臻g是n，每一個(gè)空間都有set集合。

回溯算法的總結(jié)心得第4篇都知道n皇后問(wèn)題是回溯算法解決的經(jīng)典問(wèn)題，但是用回溯解決多了組合、切割、子集、排列問(wèn)題之后，遇到這種二維矩陣還會(huì)有點(diǎn)不知所措。

首先來(lái)看一下皇后們的約束條件：

確定完約束條件，來(lái)看看究竟要怎么去搜索皇后們的位置，其實(shí)搜索皇后的位置，可以抽象為一棵樹(shù)。

下面我用一個(gè)3*3的棋盤，將搜索過(guò)程抽象為一棵樹(shù)，如圖：

從圖中，可以看出，二維矩陣中矩陣的高就是這棵樹(shù)的高度，矩陣的寬就是樹(shù)形結(jié)構(gòu)中每一個(gè)節(jié)點(diǎn)的寬度。

那么我們用皇后們的約束條件，來(lái)回溯搜索這棵樹(shù)，只要搜索到了樹(shù)的葉子節(jié)點(diǎn)，說(shuō)明就找到了皇后們的合理位置了。

按照我總結(jié)的如下回溯模板，我們來(lái)依次分析：

我依然是定義全局變量二維數(shù)組result來(lái)記錄最終結(jié)果。

參數(shù)n是棋盤的大小，然后用row來(lái)記錄當(dāng)前遍歷到棋盤的第幾層了。

代碼如下：

在如下樹(shù)形結(jié)構(gòu)中：

可以看出，當(dāng)遞歸到棋盤最底層（也就是葉子節(jié)點(diǎn)）的時(shí)候，就可以收集結(jié)果并返回了。

代碼如下：

遞歸深度就是row控制棋盤的行，每一層里for循環(huán)的col控制棋盤的列，一行一列，確定了放置皇后的位置。

每次都是要從新的一行的起始位置開(kāi)始搜，所以都是從0開(kāi)始。

代碼如下：

按照如下標(biāo)準(zhǔn)去重：

代碼如下：

在這份代碼中，細(xì)心的同學(xué)可以發(fā)現(xiàn)為什么沒(méi)有在同行進(jìn)行檢查呢？

因?yàn)樵趩螌铀阉鞯倪^(guò)程中，每一層遞歸，只會(huì)選for循環(huán)（也就是同一行）里的一個(gè)元素，所以不用去重了。

那么按照這個(gè)模板不難寫(xiě)出如下C++代碼：

可以看出，除了驗(yàn)證棋盤合法性的代碼，省下來(lái)部分就是按照回溯法模板來(lái)的。

本題是我們解決棋盤問(wèn)題的第一道題目。

如果從來(lái)沒(méi)有接觸過(guò)N皇后問(wèn)題的同學(xué)看著這樣的題會(huì)感覺(jué)無(wú)從下手，可能知道要用回溯法，但也不知道該怎么去搜。

回溯算法的總結(jié)心得第5篇題目描述：

給定一個(gè)可包含重復(fù)數(shù)字的序列

nums

，按任意順序

返回所有不重復(fù)的全排列。

?思路：這個(gè)題目求的是全排列，所以這時(shí)候就不在需要傳遞起始位置了，因?yàn)榍笕帕?，?shù)字是可以重復(fù)使用的，不同的順序是不同的結(jié)果。但是題目給定的數(shù)組有重復(fù)的元素，應(yīng)該如何去重？其實(shí)這里的去重思路和上面的題目一樣，也是在使用過(guò)這個(gè)數(shù)字，將要進(jìn)行下一次for循環(huán)的時(shí)候，看一下下一個(gè)數(shù)字是不是一樣，一樣的話就跳過(guò)，同樣也需要對(duì)原數(shù)組進(jìn)行排序。這里對(duì)原數(shù)組進(jìn)行排序也沒(méi)有影響，因?yàn)榍蟮氖侨帕校灰沁@些數(shù)字，那么最后得到的全排列一定是一樣的。好了，原數(shù)組中重復(fù)的數(shù)字問(wèn)題解決了，也就是同層有重復(fù)數(shù)字的問(wèn)題解決了。（樹(shù)層去重）

但是還有一個(gè)問(wèn)題需要考慮。我們?cè)谶f歸的時(shí)候，先把當(dāng)前拿到的數(shù)字添加到結(jié)果中，然后進(jìn)行下一次遞歸，但是因?yàn)榍笕帕?，下一次遞歸的起始位置也是0。那么可以想一下在第一次遞歸的時(shí)候，拿到的是下標(biāo)為0

的數(shù)字，下一次遞歸又是這個(gè)數(shù)字，而我們希望不要在使用現(xiàn)在使用過(guò)的這個(gè)數(shù)字了，這時(shí)候怎么辦？這一點(diǎn)其實(shí)是在縱深方向的去重，解決方法是定義一個(gè)數(shù)組用來(lái)標(biāo)定已經(jīng)使用過(guò)的數(shù)字，如果這個(gè)數(shù)字使用過(guò)了，那就進(jìn)行標(biāo)記，下次遞歸的時(shí)候只有沒(méi)有標(biāo)記的數(shù)字才可以使用，當(dāng)遞歸返回的時(shí)候，再取消標(biāo)記。其實(shí)就是回溯。這樣就可以避免下次遞歸的時(shí)候又用到了之前的遞歸使用過(guò)的數(shù)字。對(duì)樹(shù)層去重還有一個(gè)方法就是在每次遞歸的for循環(huán)之前定義一個(gè)數(shù)組，用于標(biāo)定同層使用過(guò)的數(shù)字。注意是要每次遞歸的for循環(huán)之前都要重新定義，這樣才能保證和每一層對(duì)應(yīng)。（樹(shù)枝去重）

所以總結(jié)一下，在求排列的時(shí)候，不僅要對(duì)樹(shù)層去重，還要對(duì)同一樹(shù)枝去重。

回溯算法的總結(jié)心得第6篇這個(gè)遞增子序列比較像是取有序的子集。而且本題也要求不能有相同的遞增子序列。

這又是子集，又是去重，是不是不由自主的想起了剛剛講過(guò)的90.子集II(opensnewwindow)。

就是因?yàn)樘窳?，更要注意差別所在，要不就掉坑里了！

在90.子集II(opensnewwindow)中我們是通過(guò)排序，再加一個(gè)標(biāo)記數(shù)組來(lái)達(dá)到去重的目的。

而本題求自增子序列，是不能對(duì)原數(shù)組進(jìn)行排序的，排完序的數(shù)組都是自增子序列了。

回溯算法的總結(jié)心得第7篇在for(inti=startIndex;i<();i++)循環(huán)中，我們定義了起始位置startIndex，那么[startIndex,i]就是要截取的子串。

首先判斷這個(gè)子串是不是回文，如果是回文，就加入在vectorpath中，path用來(lái)記錄切割過(guò)的回文子串。

代碼如下：

回溯算法的總結(jié)心得第8篇回溯用遞歸實(shí)現(xiàn)

遞歸是一種算法結(jié)構(gòu)，回溯是一種算法思想；一個(gè)遞歸就是在函數(shù)中調(diào)用函數(shù)本身來(lái)解決問(wèn)題；回溯就是通過(guò)不同的嘗試來(lái)生成問(wèn)題的解，有點(diǎn)類似于窮舉，但是和窮舉不同的是回溯會(huì)“剪枝”，意思就是對(duì)已經(jīng)知道錯(cuò)誤的結(jié)果沒(méi)必要再枚舉接下來(lái)的答案了，比如一個(gè)有序數(shù)列1,2,3,4,5，我要找和為5的所有集合，從前往后搜索我選了1，然后2，然后選3的時(shí)候發(fā)現(xiàn)和已經(jīng)大于預(yù)期，那么4,5肯定也不行，這就是一種對(duì)搜索過(guò)程的優(yōu)化。

（1）首先要將問(wèn)題轉(zhuǎn)化，得出解空間樹(shù)。這棵樹(shù)的每條完整路徑都代表了一種解的可能。通過(guò)深度優(yōu)先搜索這棵樹(shù)，枚舉每種可能的解的情況；從而得出結(jié)果。但是回溯法搜索解空間樹(shù)時(shí)，通常采用兩種策略來(lái)避免無(wú)效搜索，提高回溯法的搜索效率。

（2）回溯法的實(shí)現(xiàn)步驟

通過(guò)讀題完成下面三個(gè)步驟：1)描述解的形式，定義一個(gè)解空間，它包含問(wèn)題的所有解。2)構(gòu)造狀態(tài)空間樹(shù)。3)構(gòu)造約束函數(shù)（用于殺死節(jié)點(diǎn)）。然后就要通過(guò)深度優(yōu)先搜索思想完成回溯，完整過(guò)程如下：1)設(shè)置初始化的方案（給變量賦初值，讀入已知數(shù)據(jù)等）。2)變換方式去試探，若全部試完則轉(zhuǎn)(7)。3)判斷此法是否成功（通過(guò)約束函數(shù)），不成功則轉(zhuǎn)(2)。4)試探成功則前進(jìn)一步再試探。5)正確方案還未找到則轉(zhuǎn)(2)。6)已找到一種方案則記錄并打印。7)退回一步（回溯），若未退到頭則轉(zhuǎn)(2)。8)已退到頭則結(jié)束或打印無(wú)解

子集樹(shù)和排列數(shù)是回溯法解題時(shí)常用的兩個(gè)典型的解空間樹(shù)

所給的問(wèn)題是從n個(gè)元素的集合S中找出滿足某種性質(zhì)的子集時(shí)，相應(yīng)的解空間成為子集樹(shù)。如0-1背包問(wèn)題，從所給重量、價(jià)值不同的物品中挑選幾個(gè)物品放入背包，使得在滿足背包不超重的情況下，背包內(nèi)物品價(jià)值最大。它的解空間就是一個(gè)典型的子集樹(shù)。

在這想到了圖的遍歷的深度優(yōu)先搜索算法，對(duì)比一下

深度優(yōu)先搜索基本模型（其實(shí)和子集樹(shù)模板一樣）

待完善

所給的問(wèn)題是確定n個(gè)元素滿足某種性質(zhì)的排列時(shí)，相應(yīng)的解空間就是排列樹(shù)。如旅行售貨員問(wèn)題，一個(gè)售貨員把幾個(gè)城市旅行一遍，要求走的路程最小。它的解就是幾個(gè)城市的排列，解空間就是排列樹(shù)。

待完善...

回溯算法的總結(jié)心得第9篇本題這涉及到兩個(gè)關(guān)鍵問(wèn)題：

相信這里不同的切割方式可以搞懵很多同學(xué)了。

這種題目，想用for循環(huán)暴力解法，可能都不那么容易寫(xiě)出來(lái)，所以要換一種暴力的方式，就是回溯。

一些同學(xué)可能想不清楚回溯究竟是如何切割字符串呢？

我們來(lái)分析一下切割，其實(shí)切割問(wèn)題類似組合問(wèn)題。

例如對(duì)于字符串a(chǎn)bcdef：

感受出來(lái)了不？

所以切割問(wèn)題，也可以抽象為一棵樹(shù)形結(jié)構(gòu)，如圖：

遞歸用來(lái)縱向遍歷，for循環(huán)用來(lái)橫向遍歷，切割線（就是圖中的紅線）切割到字符串的結(jié)尾位置，說(shuō)明找到了一個(gè)切割方法。

此時(shí)可以發(fā)現(xiàn)，切割問(wèn)題的回溯搜索的過(guò)程和組合問(wèn)題的回溯搜索的過(guò)程是差不多的。

全局變量數(shù)組path存放切割后回文的子串，二維數(shù)組result存放結(jié)果集。（這兩個(gè)參數(shù)可以放到函數(shù)參數(shù)里）

本題遞歸函數(shù)參數(shù)還需要startIndex，因?yàn)榍懈钸^(guò)的地方，不能重復(fù)切割，和組合問(wèn)題也是保持一致的。

在回溯算法：求組合總和（二）(opensnewwindow)中我們深入探討了組合問(wèn)題什么時(shí)候需要startIndex，什么時(shí)候不需要startIndex。

代碼如下：

從樹(shù)形結(jié)構(gòu)的圖中可以看出：切割線切到了字符串最后面，說(shuō)明找到了一種切割方法，此時(shí)就是本層遞歸的終止條件。

回溯算法的總結(jié)心得第10篇選擇過(guò)程樹(shù)形結(jié)構(gòu)如圖所示：

可以看到圖中，每個(gè)節(jié)點(diǎn)相對(duì)于39.組合總和(opensnewwindow)我多加了used數(shù)組，這個(gè)used數(shù)組下面會(huì)重點(diǎn)介紹。

與39.組合總和(opensnewwindow)套路相同，此題還需要加一個(gè)bool型數(shù)組used，用來(lái)記錄同一樹(shù)枝上的元素是否使用過(guò)。

這個(gè)集合去重的重任就是used來(lái)完成的。

代碼如下：

與39.組合總和(opensnewwindow)相同，終止條件為sum>target和sum==target。

代碼如下：

sum>target這個(gè)條件其實(shí)可以省略，因?yàn)樵谶f歸單層遍歷的時(shí)候，會(huì)有剪枝的操作，下面會(huì)介紹到。

前面我們提到：要去重的是“同一樹(shù)層上的使用過(guò)”，如何判斷同一樹(shù)層上元素（相同的元素）是否使用過(guò)了呢。

回溯算法的總結(jié)心得第11篇所以搜索的過(guò)程中就是要不斷的刪multiset里的元素，那么推薦使用unordered_map>targets。

在遍歷unordered_map<出發(fā)機(jī)場(chǎng),map<到達(dá)機(jī)場(chǎng),航班次數(shù)>>targets的過(guò)程中，可以使用_航班次數(shù)_這個(gè)字段的數(shù)字做相應(yīng)的增減，來(lái)標(biāo)記到達(dá)機(jī)場(chǎng)是否使用過(guò)了。

如果“航班次數(shù)”大于零，說(shuō)明目的地還可以飛，如果“航班次數(shù)”等于零說(shuō)明目的地不能飛了，而不用對(duì)集合做刪除元素或者增加元素的操作。

回溯算法的總結(jié)心得第12篇咋整？

回溯搜索法來(lái)了，雖然回溯法也是暴力，但至少能寫(xiě)出來(lái)，不像for循環(huán)嵌套k層讓人絕望。

那么回溯法怎么暴力搜呢？

上面我們說(shuō)了要解決n為100，k為50的情況，暴力寫(xiě)法需要嵌套50層for循環(huán)，那么回溯法就用遞歸來(lái)解決嵌套層數(shù)的問(wèn)題。

遞歸來(lái)做層疊嵌套（可以理解是開(kāi)k層for循環(huán)），每一次的遞歸中嵌套一個(gè)for循環(huán)，那么遞歸就可以用于解決多層嵌套循環(huán)的問(wèn)題了。

此時(shí)遞歸的層數(shù)大家應(yīng)該知道了，例如：n為100，k為50的情況下，就是遞歸50層。

一些同學(xué)本來(lái)對(duì)遞歸就懵，回溯法中遞歸還要嵌套for循環(huán)，可能就直接暈倒了！

如果腦洞模擬回溯搜索的過(guò)程，絕對(duì)可以讓人窒息，所以需要抽象圖形結(jié)構(gòu)來(lái)進(jìn)一步理解。

回溯算法的總結(jié)心得第13篇題目描述：

n

皇后問(wèn)題研究的是如何將n

個(gè)皇后放置在n×n的棋盤上，并且使皇后彼此之間不能相互攻擊。給你一個(gè)整數(shù)n，返回所有不同的

n

皇后問(wèn)題的解決方案。每一種解法包含一個(gè)不同的

n皇后問(wèn)題的棋子放置方案，該方案中'Q'和'.'分別代表了皇后和空位。

思路：這一題和前面的也是類似，這一次需要判斷的是當(dāng)前要放置棋子的位置是否合法。這里的棋子是皇后，這里普及一點(diǎn)點(diǎn)國(guó)際象棋小知識(shí)，皇后可以橫著、豎著、斜著走。所以這里的合法判斷就變成了判斷當(dāng)前位置的同行、同列、斜線是否存在皇后。這里一定要想清楚斜著走的話，行和列是怎么加減的，而且只需要向上判斷，因?yàn)橄旅娴钠灞P還沒(méi)處理。

首先進(jìn)行棋盤的初始化，定義一個(gè)字符串?dāng)?shù)組，并全部初始化為題目要求的點(diǎn)。然后就開(kāi)始進(jìn)行遞歸，遞歸的是需要期盼的大小，棋盤和當(dāng)前所在的行數(shù)。因?yàn)橐恍锌隙ㄖ荒芊乓粋€(gè)皇后，所以以行為單位進(jìn)行for循環(huán)。在遞歸之前進(jìn)行條件判斷即可，是合法的位置就變?yōu)榛屎?，然后進(jìn)行遞歸，如果不是合法的位置，那就進(jìn)行下一輪循環(huán)，看看這一行的下一個(gè)位置合不合法。遞歸返回時(shí)記得要回溯，撤銷之前的操作。

回溯算法的總結(jié)心得第14篇這道題目我使用回溯法，那么下面按照我總結(jié)的回溯模板來(lái)：

本題以輸入：[[“JFK”,“KUL”],[“JFK”,“NRT”],[“NRT”,“JFK”]為例，抽象為樹(shù)形結(jié)構(gòu)如下：

開(kāi)始回溯三部曲講解：

在講解映射關(guān)系的時(shí)候，已經(jīng)講過(guò)了，使用unordered_map>targets;來(lái)記錄航班的映射關(guān)系，我定義為全局變量。

當(dāng)然把參數(shù)放進(jìn)函數(shù)里傳進(jìn)去也是可以的，我是盡量控制函數(shù)里參數(shù)的長(zhǎng)度。

參數(shù)里還需要ticketNum，表示有多少個(gè)航班（終止條件會(huì)用上）。

代碼如下：

回溯算法的總結(jié)心得第15篇題目描述：

給定一個(gè)候選人編號(hào)的集合

candidates

和一個(gè)目標(biāo)數(shù)

target

，找出

candidates

中所有可以使數(shù)字和為

target

的組合。candidates

中的每個(gè)數(shù)字在每個(gè)組合中只能使用

一次

。注意：解集不能包含重復(fù)的組合。

思路：這個(gè)題有一個(gè)特殊情況，那就是給定的數(shù)組中可能會(huì)有重復(fù)的元素，那么如果這個(gè)元素使用過(guò)了，后面再使用，那就會(huì)導(dǎo)致重復(fù)，但是我們又不能在一開(kāi)始就刪除掉重復(fù)的元素，否則就和給定的數(shù)組不一樣了，結(jié)果肯定會(huì)不正確。所以我們只能在遍歷的時(shí)候，一邊遍歷，一邊進(jìn)行去重的操作。

我的去重思路是這樣：我們按照正常的遞歸回溯先操作，當(dāng)遞歸返回的時(shí)候，將要進(jìn)行下一次FOR循環(huán)

的時(shí)候，進(jìn)行去重，如果下一個(gè)數(shù)字和這個(gè)使用過(guò)的數(shù)字是一樣的，那就跳過(guò)，注意要是用while循環(huán)跳過(guò)，因?yàn)榭赡懿恢挂粋€(gè)重復(fù)的。要想進(jìn)行這樣的操作必須首先對(duì)原數(shù)組進(jìn)行排序，讓相同的元素挨在一起。可是排序?qū)υ瓟?shù)組進(jìn)行了修改，不會(huì)導(dǎo)致其它問(wèn)題嗎？這里我們找的是組合，和順序沒(méi)有關(guān)系，只要是這些數(shù)字，找到的就是這些組合，不會(huì)因?yàn)閿?shù)組的順序變化而導(dǎo)致組合的變化。

回溯算法的總結(jié)心得第16篇題目描述：

編寫(xiě)一個(gè)程序，通過(guò)填充空格來(lái)解決數(shù)獨(dú)問(wèn)題。數(shù)獨(dú)的解法需遵循如下規(guī)則：

數(shù)字

1-9

在每一行只能出現(xiàn)一次。數(shù)字

1-9

在每一列只能出現(xiàn)一次。數(shù)字

1-9

在每一個(gè)以粗實(shí)線分隔的

3x3

宮內(nèi)只能出現(xiàn)一次。（請(qǐng)參考示例圖）數(shù)獨(dú)部分空格內(nèi)已填入了數(shù)字，空白格用

'.'

表示。

思路：看到這個(gè)題，回想起了之前上中學(xué)被數(shù)獨(dú)游戲支配的恐懼，要是中學(xué)的時(shí)候會(huì)這個(gè)那多好，哈哈。這個(gè)題其實(shí)本質(zhì)上還是換湯不換藥，只不過(guò)遞歸時(shí)要進(jìn)行的條件判斷復(fù)雜了一些。

合法判斷：同行、同列不能有重復(fù)數(shù)字，當(dāng)前這個(gè)3*3的格子內(nèi)不能有重復(fù)數(shù)字。確定每一個(gè)小格子的起始位置想了挺久，后來(lái)發(fā)現(xiàn)是自己想復(fù)雜了，直接用當(dāng)前行除以3然后在*3，那就是起始位置，其實(shí)是利用了整形除法的取整特性。本質(zhì)上還是映射，就是把這個(gè)格子內(nèi)的行列數(shù)都映射在這個(gè)格子的起始位置。

整體思路：利用兩個(gè)for循環(huán)，遍歷每一個(gè)位置，如果這個(gè)位置是數(shù)字，那就跳過(guò)，直接遍歷下一個(gè)數(shù)字，如果是空格，那就對(duì)這個(gè)位置以及要放的數(shù)字進(jìn)行合法判斷，如果合法那就添加一個(gè)數(shù)字，如果不合法那就換一個(gè)數(shù)字再判斷。如果這9個(gè)數(shù)字都用完了還不合法，那就無(wú)解。

這里的遞歸函數(shù)也有返回值，因?yàn)槿绻业搅撕戏ǖ臄?shù)獨(dú)解，后面的就不用再遍歷了。

回溯算法的總結(jié)心得第17篇一些寫(xiě)法，是把回溯的過(guò)程放在遞歸函數(shù)里了，例如如下代碼，我可以寫(xiě)成這樣：（注意注釋中不一樣的地方）

我不建議把回溯藏在遞歸的參數(shù)里這種寫(xiě)法，很不直觀，我在二叉樹(shù)：以為使用了遞歸，其實(shí)還隱藏著回溯(opensnewwindow)這篇文章中也深度分析了，回溯隱藏在了哪里。

所以大家可以按照版本一來(lái)寫(xiě)就可以了。

4.組合總和

給你一個(gè)無(wú)重復(fù)元素的整數(shù)數(shù)組candidates和一個(gè)目標(biāo)整數(shù)target，找出candidates中可以使數(shù)字和為目標(biāo)數(shù)target的所有不同組合，并以列表形式返回。你可以按任意順序返回這些組合。

candidates中的同一個(gè)數(shù)字可以無(wú)限制重復(fù)被選取。如果至少一個(gè)數(shù)字的被選數(shù)量不同，則兩種組合是不同的。

對(duì)于給定的輸入，保證和為target的不同組合數(shù)少于150個(gè)。

回溯算法的總結(jié)心得第18篇從示例上來(lái)說(shuō)，輸入_23_，最直接的想法就是兩層for循環(huán)遍歷了吧，正好把組合的情況都輸出了。

如果輸入_233_呢，那么就三層for循環(huán)，如果_2333_呢，就四層for循環(huán)…

大家應(yīng)該感覺(jué)出和77.組合(opensnewwindow)遇到的一樣的問(wèn)題，就是這for循環(huán)的層數(shù)如何寫(xiě)出來(lái)，此時(shí)又是回溯法登場(chǎng)的時(shí)候了。

理解本題后，要解決如下三個(gè)問(wèn)題：

可以使用map或者定義一個(gè)二維數(shù)組，例如：stringletterMap[10]，來(lái)做映射，我這里定義一個(gè)二維數(shù)組，代碼如下：

例如：輸入：“23”，抽象為樹(shù)形結(jié)構(gòu)，如圖所示：

圖中可以看出遍歷的深度，就是輸入_23_的長(zhǎng)度，而葉子節(jié)點(diǎn)就是我們要收集的結(jié)果，輸出[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]。

回溯三部曲：

首先需要一個(gè)字符串s來(lái)收集葉子節(jié)點(diǎn)的結(jié)果，然后用一個(gè)字符串?dāng)?shù)組result保存起來(lái)，這兩個(gè)變量我依然定義為全局。

再來(lái)看參數(shù)，參數(shù)指定是有題目中給的stringdigits，然后還要有一個(gè)參數(shù)就是int型的index。

這個(gè)index是記錄遍歷第幾個(gè)數(shù)字了，就是用來(lái)遍歷digits的（題目中給出數(shù)字字符串），同時(shí)index也表示樹(shù)的深度。

代碼如下：

例如輸入用例_23_，兩個(gè)數(shù)字，那么根節(jié)點(diǎn)往下遞歸兩層就可以了，葉子節(jié)點(diǎn)就是要收集的結(jié)果集。

那么終止條件就是如果index等于輸入的數(shù)字個(gè)數(shù)（）了（本來(lái)index就是用來(lái)遍歷digits的）。

然后收集結(jié)果，結(jié)束本層遞歸。

代碼如下：

首先要取index指向的數(shù)字，并找到對(duì)應(yīng)的字符集（手機(jī)鍵盤的字符集）。

然后for循環(huán)來(lái)處理這個(gè)字符集，代碼如下：

注意：輸入1*#按鍵等等異常情況

代碼中最好考慮這些異常情況，但題目的測(cè)試數(shù)據(jù)中應(yīng)該沒(méi)有異常情況的數(shù)據(jù)，所以我就沒(méi)有加了。

回溯算法的總結(jié)心得第19篇題目描述：

有效IP地址正好由四個(gè)整數(shù)（每個(gè)整數(shù)位于0到255之間組成，且不能含有前導(dǎo)0），整數(shù)之間用'.'分隔。

例如：__和__是有效IP地址，但是__、__和__是無(wú)效IP地址。給定一個(gè)只包含數(shù)字的字符串s，用以表示一個(gè)IP地址，返回所有可能的有效IP地址，這些地址可以通過(guò)在s中插入

'.'來(lái)形成。你不能

重新排序或刪除s中的任何數(shù)字。你可以按任何順序返回答案。

思路：這一題和上面一題的思路是一樣的，只不過(guò)判斷條件變了，然后多了一個(gè)插入字符的操作，并且是在原字符數(shù)組上進(jìn)行操作。那么如何保證在原字符數(shù)字上操作，不會(huì)影響之后的遍歷呢？答案就是回溯，當(dāng)遞歸返回的時(shí)候，一切又會(huì)恢復(fù)原樣。那終止條件是什么呢？根據(jù)題目，這些字符串一定會(huì)被分為4段，也就是會(huì)添加3個(gè)點(diǎn)，我們可以用一個(gè)變量記錄添加點(diǎn)的個(gè)數(shù)，如果這個(gè)添加點(diǎn)的個(gè)數(shù)等于3，那就終止。注意這里的變量是從0開(kāi)始的，其實(shí)變量值等于2的時(shí)候就是插入3個(gè)點(diǎn)了，但是還會(huì)進(jìn)行下次一遞歸，這時(shí)候就變成3了。

這里需要注意的點(diǎn)：在終止的時(shí)候，要對(duì)最后這一段子串進(jìn)行合法判斷，之后最后這一段也合法，這才是一個(gè)合理的劃分。還有一個(gè)就是如果當(dāng)前子串不合法，應(yīng)該進(jìn)行下一輪循環(huán)還是直接終止循環(huán)？答案是終止，因?yàn)檫@個(gè)題目和上一個(gè)題目不一樣，這個(gè)題目如果當(dāng)前子串不合法，那么不管在加多少字符，這個(gè)子串都不合法，所以直接終止。

回溯算法的總結(jié)心得第20篇題目描述：

給你一個(gè)整數(shù)數(shù)組nums，找出并返回所有該數(shù)組中不同的遞增子序列，遞增子序列中至少有兩個(gè)元素。你可以按任意順序返回答案。數(shù)組中可能含有重復(fù)元素，如出現(xiàn)兩個(gè)整數(shù)相等，也可以視作遞增序列的一種特殊情況。

?思路：這一題其實(shí)也是換湯不換藥，但是這是一個(gè)求組合的題目，需要起始位置。不同點(diǎn)是加入的條件判斷變成了只有比當(dāng)前保存的結(jié)果數(shù)組最后一個(gè)數(shù)字大的才能加入這個(gè)結(jié)果數(shù)組，這樣可以保證這個(gè)結(jié)果數(shù)組是升序。但是這個(gè)題目給定的數(shù)組是有重復(fù)的數(shù)字的，如果重復(fù)使用就會(huì)導(dǎo)致出現(xiàn)重復(fù)的序列。而且我們不能對(duì)這個(gè)原數(shù)組進(jìn)行排序，然后按照之前總結(jié)過(guò)的當(dāng)時(shí)去重，因?yàn)檫@個(gè)題目涉及到求子序列，改變?cè)瓟?shù)組的順序會(huì)改變子序列的順序。那么我們只能用之前總結(jié)過(guò)的樹(shù)層去重，在遞歸的for循環(huán)之前定義一個(gè)數(shù)組標(biāo)記當(dāng)前樹(shù)層使用過(guò)的數(shù)字，后面在加入對(duì)是否使用過(guò)的判斷條件即可。

小陷阱：在終止條件這里，每當(dāng)結(jié)果數(shù)組大小大于2的時(shí)候，就可以作為一個(gè)升序子序列了，但是這里一定不能直接返回，因?yàn)檫@個(gè)題目不是求最終的結(jié)果，而是相當(dāng)于從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的每一個(gè)節(jié)點(diǎn)，只要符合條件都是一個(gè)升序子序列。那什么時(shí)候返回呢？起始位置超過(guò)數(shù)組最后一個(gè)位置的下標(biāo)的時(shí)候就終止了。

回溯算法的總結(jié)心得第21篇題目描述：

給定兩個(gè)整數(shù)

n

和

k，返回范圍

[1,n]

中所有可能的

k

個(gè)數(shù)的組合。你可以按

任何順序

返回答案。

思路：用這個(gè)題來(lái)整理一下回溯問(wèn)題的模板。題目的意思其實(shí)就是找組合，組合的元素個(gè)數(shù)是K。組合無(wú)序，所以使用過(guò)的數(shù)字不能再使用，否則就重復(fù)了，所以越往后找其實(shí)需要遍歷的越少。

遞歸函數(shù)參數(shù)：需要三個(gè)，分別是起始位置、要求的區(qū)間末尾數(shù)字、組合的大小。凡是組合類的問(wèn)題，都需要一個(gè)起始位置作為參數(shù)，因?yàn)橄乱粋€(gè)遞歸需要從下一個(gè)位置開(kāi)始。遞歸函數(shù)一般不需要返回值，但也有例外情況，有的情況加上一個(gè)返回值會(huì)提高搜索效率。

遞歸的邏輯：把當(dāng)前的數(shù)字添加到結(jié)果中，然后在遞歸下一個(gè)數(shù)字。當(dāng)遞歸返回時(shí)再?gòu)棾觥?/p>

遞歸終止條件：只要當(dāng)前的結(jié)果大小等于K，那這就是一個(gè)符合條件的結(jié)果，添加到結(jié)果集中。

回溯算法的總結(jié)心得第22篇題目描述：

給定一個(gè)僅包含數(shù)字

2-9

的字符串，返回所有它能表示的字母組合。答案可以按任意順序返回。給出數(shù)字到字母的映射如下（與電話按鍵相同）。注意1不對(duì)應(yīng)任何字母。

思路：這一題剛拿到肯定會(huì)有點(diǎn)懵，感覺(jué)好像知道要怎么做，但是具體的細(xì)節(jié)又不是很清楚，其實(shí)這是因?yàn)閷?duì)水回溯還沒(méi)有完全理解。拿到這樣的題，首先第一步要建立映射關(guān)系，也就是把按鍵和字母對(duì)應(yīng)起來(lái)。這道題目肯定是建立一個(gè)字符串?dāng)?shù)組了，因?yàn)槊恳粋€(gè)按鍵上有多個(gè)字母，到時(shí)候肯定要用到其中一個(gè)或幾個(gè)，需要遍歷。

其次要考慮一下，如何對(duì)輸入的數(shù)字進(jìn)行拆分。例如輸入了23，我們要分別對(duì)2和3對(duì)應(yīng)的字符串進(jìn)行梳理，如果輸入234，那就分別對(duì)2，3和4對(duì)應(yīng)的字符串進(jìn)行處理。其實(shí)就是在N個(gè)數(shù)組中找所有的組合。之前做過(guò)在一個(gè)數(shù)組中找組合的，現(xiàn)在變成了N個(gè)。

關(guān)鍵點(diǎn)：用一個(gè)index表示現(xiàn)在用到的是輸入數(shù)字的第幾個(gè)數(shù)字。例如輸入23，那么index=0表示現(xiàn)在使用的是2，index=1表示現(xiàn)在使用的是3。而用這個(gè)index可以拿到這個(gè)數(shù)字對(duì)應(yīng)的數(shù)組。拿到這個(gè)數(shù)組就可以進(jìn)行遞歸遍歷了。

回溯算法的總結(jié)心得第23篇這里給出Carl總結(jié)的回溯算法模板。

在講二叉樹(shù)的遞歸(opensnewwindow)中我們說(shuō)了遞歸三部曲，這里我再給大家列出回溯三部曲。

在回溯算法中，我的習(xí)慣是函數(shù)起名字為backtracking，這個(gè)起名大家隨意。

回溯算法中函數(shù)返回值一般為void。

再來(lái)看一下參數(shù)，因?yàn)榛厮菟惴ㄐ枰膮?shù)可不像二叉樹(shù)遞歸的時(shí)候那么容易一次性確定下來(lái)，所以一般是先寫(xiě)邏輯，然后需要什么參數(shù)，就填什么參數(shù)。

但后面的回溯題目的講解中，為了方便大家理解，我在一開(kāi)始就幫大家把參數(shù)確定下來(lái)。

回溯函數(shù)偽代碼如下：

既然是樹(shù)形結(jié)構(gòu)，那么我們?cè)谥v解二叉樹(shù)的遞歸(opensnewwindow)的時(shí)候，就知道遍歷樹(shù)形結(jié)構(gòu)一定要有終止條件。

所以回溯也有要終止條件。

什么時(shí)候達(dá)到了終止條件，樹(shù)中就可以看出，一般來(lái)說(shuō)搜到葉子節(jié)點(diǎn)了，也就找到了滿足條件的一條答案，把這個(gè)答案存放起來(lái)，并結(jié)束本層遞歸。

所以回溯函數(shù)終止條件偽代碼如下：

在上面我們提到了，回溯法一般是在集合中遞歸搜索，集合的大小構(gòu)成了樹(shù)的寬度，遞歸的深度構(gòu)成的樹(shù)的深度。

如圖：

注意圖中，我特意舉例集合大小和孩子的數(shù)量是相等的！

回溯函數(shù)遍歷過(guò)程偽代碼如下：

for循環(huán)就是遍歷集合區(qū)間，可以理解一個(gè)節(jié)點(diǎn)有多少個(gè)孩子，這個(gè)for循環(huán)就執(zhí)行多少次。

backtracking這里自己調(diào)用自己，實(shí)現(xiàn)遞歸。

大家可以從圖中看出for循環(huán)可以理解是橫向遍歷，backtracking（遞歸）就是縱向遍歷，這樣就把這棵樹(shù)全遍歷完了，一般來(lái)說(shuō)，搜索葉子節(jié)點(diǎn)就是找的其中一個(gè)結(jié)果了。

分析完過(guò)程，回溯算法模板框架如下：

回溯算法的總結(jié)心得第24篇題目描述：

給你一個(gè)字符串

s，請(qǐng)你將s分割成一些子串，使每個(gè)子串都是

回文串

。返回

s

所有可能的分割方案。回文串

是正著讀和反著讀都一樣的字符串。?

?思路：這個(gè)題目其實(shí)本質(zhì)上就是一個(gè)回溯遞歸，只不過(guò)是在每次遞歸的時(shí)候要多進(jìn)行一個(gè)條件判斷，這個(gè)條件判斷就是判斷是不是回文串。判斷回文串這里就不說(shuō)了，雙指針搞定。

整體思路就是利用遞歸，當(dāng)前子串是回文串，那就遞歸，從下一個(gè)字符繼續(xù)開(kāi)始找是不是回文串。如果當(dāng)前子串不是回文串，那就直接進(jìn)行下一輪循環(huán)，看看再加進(jìn)來(lái)一個(gè)字符是不是回文串。最后當(dāng)開(kāi)始位置大于等于數(shù)組的末尾的時(shí)候，是一個(gè)符合的結(jié)果，就把當(dāng)前結(jié)果添加到結(jié)果集中。

這里有一個(gè)陷阱：要記住每次拿到的是