前言

回溯算法是一個非常經(jīng)典的算法，像圖中的DFS（深度優(yōu)先遍歷）其核心思想就是回溯，但是初學(xué)者對于回溯總是感覺一頭霧水，不知所措，但熟不知，回溯算法也是尤其“套路”的

原創(chuàng)聲明

本人在學(xué)習(xí)回溯算法時也感覺比較困惑，但是有幸看到一本非常好的算法書籍，也算是解決了我很多疑惑，我發(fā)現(xiàn)有些東西不是我智商不夠，而是缺乏訓(xùn)練，尤其是有目的，有邏輯的訓(xùn)練。
本文皆是我在閱讀它的書后所做的一些整理，發(fā)表一下自己的看法。如果有興趣的小伙伴可以移步

labuladong的算法小抄

題目

一：回溯算法的本質(zhì)和框架（結(jié)合全排列）

（1）回溯算法的本質(zhì)

回溯算法本質(zhì)是一個暴力窮舉的過程，你會發(fā)現(xiàn)涉及回溯算法的題目都有一個共同特點(diǎn)：列出所有滿足的情況
而且做得多了，你也會有種感覺，就是每個能用回溯算法解決的題目總能畫出一個二叉樹來，比如LeetCode 46：全排列這就是一道打開回溯算法大門的經(jīng)典題，而它對應(yīng)的二叉樹是這樣的

在回溯算法中，我們稱這樣的樹為決策樹，解決一個回溯問題，其實(shí)就是一個決策樹的遍歷過程

（2）回溯算法的框架

遍歷整個決策樹時，你只需要思考三個問題：

• 路徑：你已經(jīng)做出的選擇
• 選擇列表：也就是你當(dāng)前可以做的選擇
• 結(jié)束條件：到達(dá)決策樹底層，無法再做選擇的條件

以全排列為例：說明上面的含義，全排列的決策樹如下

完成全排列，這三個位置的數(shù)字是不能夠重復(fù)的，所以假如你站到了根節(jié)點(diǎn)上，你就可以做出決策了，你現(xiàn)在可以選擇1或2或3，為什么呢，因?yàn)閯傞_始你還沒有做出選擇；好的現(xiàn)在你做出了選擇，選擇了2，也就是到達(dá)了紅色的結(jié)點(diǎn)，那么你現(xiàn)在的路徑就是2，它記錄了你已經(jīng)做出的選擇，現(xiàn)在你可以選擇1或3，那么它就是你的選擇列表；，然后當(dāng)你走的樹的最底層時你會發(fā)現(xiàn)你沒得選擇，于是你到達(dá)了結(jié)束條件，同時此時的選擇列表為空

現(xiàn)在我們可以拿出回溯算法的框架了，解決回溯算法類的題目時，你只需要按照這種角度去思考，不能保證一定能解出來，但是至少能保證已經(jīng)非常接近正確答案了。至少能保證，你看見某個題目，即使你想不出來，但是你知道應(yīng)該怎么去靠近正確解法，因?yàn)槟懿荒芙獬鰜?#xff0c;最重要的還是要靠你的理解能力。

下面result通常設(shè)為一個全局變量，用于返回結(jié)果，前面我們就說過，回溯算法本質(zhì)就是在遍歷決策樹，所以那個backtrack其實(shí)就是在實(shí)現(xiàn)這樣的需求，下面的for循環(huán)時在做出選擇，然后再進(jìn)行backtrack遞歸。需要注意的是做選擇做出的是合理的選擇，就拿全排列而言，做選擇時一定要選擇在選擇列表中不屬于路徑的元素，通俗的講就是你已經(jīng)選擇了2，然后再選擇時候就不能選擇2了，只能選擇1或3了

result = [] def backtrack(路徑, 選擇列表):if 滿足結(jié)束條件:result.add(路徑)returnfor 選擇 in 選擇列表:做選擇backtrack(路徑, 選擇列表)撤銷選擇

上面的框架中，有一點(diǎn)我相信大家是肯定有疑惑的，那就是為什么要撤銷選擇
前面我們就說過，回溯算法本質(zhì)就是在遍歷決策樹，那么新的問題又來了：如何遍歷？如何遍歷我就不用說了，我要特別強(qiáng)調(diào)的是它的本質(zhì)，因?yàn)楹芏嗳死鲜前凑铡白笾杏摇?#xff0c;“左右中”這種方式去記憶樹的遍歷，無法體會到其精髓。
就拿前序和后序來說，你能說出其本質(zhì)是什么嗎？本質(zhì)就是它是進(jìn)入某個結(jié)點(diǎn)之前就行執(zhí)行操作還是離開某個結(jié)點(diǎn)之后再執(zhí)行操作的問題

大家可以想一想，你的一次選擇結(jié)束了，你肯定要返回當(dāng)當(dāng)時進(jìn)入遞歸時的狀態(tài)，然后進(jìn)行另外的選擇啊，不然你不返回狀態(tài)，其他選擇怎么辦。如果不撤銷，按照上圖的角度，你只會得到一個結(jié)果，就是用于遍歷的左子樹。

好的至此，基本的問題就講清楚了，我相信大家肯定還有諸多疑惑，但是沒有關(guān)系，做完全排列你就會讀回溯有了新的理解

總結(jié)

以上是生活随笔為你收集整理的【README】回溯算法基本框架的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。