[[423516]]

回溯算法其實(shí)非常晦澀難懂，建議大家配合我的B站視頻，來學(xué)習(xí)回溯算法，相信看完之后，會(huì)解開你對(duì)回溯算法的種種疑惑。

什么是回溯法

回溯法也可以叫做回溯搜索法，它是一種搜索的方式。

在二叉樹系列中，我們已經(jīng)不止一次，提到了回溯，例如二叉樹：以為使用了遞歸，其實(shí)還隱藏著回溯。

回溯是遞歸的副產(chǎn)品，只要有遞歸就會(huì)有回溯。

所以以下講解中，回溯函數(shù)也就是遞歸函數(shù)，指的都是一個(gè)函數(shù)。

回溯法的效率

回溯法的性能如何呢，這里要和大家說清楚了，雖然回溯法很難，很不好理解，但是回溯法并不是什么高效的算法。

因?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ú)等等

相信大家看著這些之后會(huì)發(fā)現(xiàn)，每個(gè)問題，都不簡(jiǎn)單!

另外，會(huì)有一些同學(xué)可能分不清什么是組合，什么是排列?

組合是不強(qiáng)調(diào)元素順序的，排列是強(qiáng)調(diào)元素順序。

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

記住組合無序，排列有序，就可以了。

如何理解回溯法

回溯法解決的問題都可以抽象為樹形結(jié)構(gòu)，是的，我指的是所有回溯法的問題都可以抽象為樹形結(jié)構(gòu)!

因?yàn)榛厮莘ń鉀Q的都是在集合中遞歸查找子集，集合的大小就構(gòu)成了樹的寬度，遞歸的深度，都構(gòu)成的樹的深度。

遞歸就要有終止條件，所以必然是一顆高度有限的樹(N叉樹)。

這塊可能初學(xué)者還不太理解，后面的回溯算法解決的所有題目中，我都會(huì)強(qiáng)調(diào)這一點(diǎn)并畫圖舉相應(yīng)的例子，現(xiàn)在有一個(gè)印象就行。

回溯法模板

這里給出Carl總結(jié)的回溯算法模板。

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

• 回溯函數(shù)模板返回值以及參數(shù)

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

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

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

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

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

void backtracking(參數(shù)) 

• 回溯函數(shù)終止條件

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

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

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

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

if (終止條件) { 
    存放結(jié)果; 
    return; 
} 

• 回溯搜索的遍歷過程

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

如圖：

回溯算法理論基礎(chǔ)

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

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

for (選擇：本層集合中元素（樹中節(jié)點(diǎn)孩子的數(shù)量就是集合的大小）) { 
    處理節(jié)點(diǎn); 
    backtracking(路徑，選擇列表); // 遞歸 
    回溯，撤銷處理結(jié)果 
} 

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é)果了。

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

void backtracking(參數(shù)) { 
    if (終止條件) { 
        存放結(jié)果; 
        return; 
    } 
 
    for (選擇：本層集合中元素（樹中節(jié)點(diǎn)孩子的數(shù)量就是集合的大?。? { 
        處理節(jié)點(diǎn); 
        backtracking(路徑，選擇列表); // 遞歸 
        回溯，撤銷處理結(jié)果 
    } 
} 

這份模板很重要，后面做回溯法的題目都靠它了!

如果從來沒有學(xué)過回溯算法的錄友們，看到這里會(huì)有點(diǎn)懵，后面開始講解具體題目的時(shí)候就會(huì)好一些了，已經(jīng)做過回溯法題目的錄友，看到這里應(yīng)該會(huì)感同身受了。

總結(jié)

本篇我們講解了，什么是回溯算法，知道了回溯和遞歸是相輔相成的。

接著提到了回溯法的效率，回溯法其實(shí)就是暴力查找，并不是什么高效的算法。

然后列出了回溯法可以解決幾類問題，可以看出每一類問題都不簡(jiǎn)單。

最后我們講到回溯法解決的問題都可以抽象為樹形結(jié)構(gòu)(N叉樹)，并給出了回溯法的模板。