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

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

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

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

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

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

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

和這么寫：

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

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

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

直接這樣寫不就完事了？

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

是不是豁然開朗了??！

13.重新安排行程

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

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

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

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

組合問題：N個(gè)數(shù)??按?定規(guī)則找出k個(gè)數(shù)的集合切割問題：?個(gè)字符串按?定規(guī)則有?種切割?式?集問題：?個(gè)N個(gè)數(shù)的集合?有多少符合條件的?集排列問題：N個(gè)數(shù)按?定規(guī)則全排列，有?種排列?式棋盤問題：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)，是不是開始窒息。此時(shí)就會(huì)發(fā)現(xiàn)雖然想暴?搜索，但是?for循環(huán)嵌套連暴?都寫不出來！

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

接下來看?下優(yōu)化過程如下：

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

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

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

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

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

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

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

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

首先來看一下皇后們的約束條件：

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

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

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

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

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

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

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

代碼如下：

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

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

代碼如下：

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

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

代碼如下：

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

代碼如下：

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

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

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

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

本題是我們解決棋盤問題的第一道題目。

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

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

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

nums

，按任意順序

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

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

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

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

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

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

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

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

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

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

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

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

代碼如下：

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

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

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

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

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

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

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

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

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

待完善

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

待完善...

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

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

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

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

我們來分析一下切割，其實(shí)切割問題類似組合問題。

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

感受出來了不？

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

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

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

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

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

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

代碼如下：

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

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

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

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

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

代碼如下：

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

代碼如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

n

皇后問題研究的是如何將n

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

n

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

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

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

首先進(jìn)行棋盤的初始化，定義一個(gè)字符串?dāng)?shù)組，并全部初始化為題目要求的點(diǎn)。然后就開始進(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é)的回溯模板來：

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

開始回溯三部曲講解：

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

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

參數(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è)元素使用過了，后面再使用，那就會(huì)導(dǎo)致重復(fù)，但是我們又不能在一開始就刪除掉重復(fù)的元素，否則就和給定的數(shù)組不一樣了，結(jié)果肯定會(huì)不正確。所以我們只能在遍歷的時(shí)候，一邊遍歷，一邊進(jìn)行去重的操作。

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

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

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

編寫一個(gè)程序，通過填充空格來解決數(shù)獨(dú)問題。數(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ì)上還是換湯不換藥，只不過遞歸時(shí)要進(jìn)行的條件判斷復(fù)雜了一些。

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

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

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

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

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

所以大家可以按照版本一來寫就可以了。

4.組合總和

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

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

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

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

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

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

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

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

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

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

回溯三部曲：

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

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

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

代碼如下：

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

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

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

代碼如下：

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

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

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

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

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

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

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

'.'來形成。你不能

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

思路：這一題和上面一題的思路是一樣的，只不過判斷條件變了，然后多了一個(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開始的，其實(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é)過的當(dāng)時(shí)去重，因?yàn)檫@個(gè)題目涉及到求子序列，改變?cè)瓟?shù)組的順序會(huì)改變子序列的順序。那么我們只能用之前總結(jié)過的樹層去重，在遞歸的for循環(huán)之前定義一個(gè)數(shù)組標(biāo)記當(dāng)前樹層使用過的數(shù)字，后面在加入對(duì)是否使用過的判斷條件即可。

小陷阱：在終止條件這里，每當(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í)候返回呢？起始位置超過數(shù)組最后一個(gè)位置的下標(biāo)的時(shí)候就終止了。

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

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

n

和

k，返回范圍

[1,n]

中所有可能的

k

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

任何順序

返回答案。

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

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

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

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

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

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

2-9

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

思路：這一題剛拿到肯定會(huì)有點(diǎn)懵，感覺好像知道要怎么做，但是具體的細(xì)節(jié)又不是很清楚，其實(shí)這是因?yàn)閷?duì)水回溯還沒有完全理解。拿到這樣的題，首先第一步要建立映射關(guān)系，也就是把按鍵和字母對(duì)應(yīng)起來。這道題目肯定是建立一個(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ù)組中找所有的組合。之前做過在一個(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é)的回溯算法模板。

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

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

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

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

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

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

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

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

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

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

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

如圖：

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

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

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

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

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

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

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

給你一個(gè)字符串

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

回文串

。返回

s

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

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

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

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

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