[[345679]]

 前言
這次梳理的是回溯算法，掌握它的解決問(wèn)題思路，對(duì)很多搜索嘗試問(wèn)題，都會(huì)在日后學(xué)習(xí)工作中有所幫助。

我對(duì)回溯算法有一定理解：回溯算法建立在DFS基礎(chǔ)之上的，但不同的是在搜索的過(guò)程中，達(dá)到結(jié)束條件后，恢復(fù)狀態(tài)，回溯上一層，再次搜索，因此我們可以這樣子理解，回溯算法與DFS的區(qū)別就是有無(wú)狀態(tài)重置。

如果你還不了解什么是回溯算法，或者知道一些，但是對(duì)于它具體是如何實(shí)現(xiàn)回溯，那么這篇文章可能適合你閱讀。

那么圍繞以下幾個(gè)點(diǎn)來(lái)展開(kāi)介紹回溯算法👇

• 來(lái)源
• 基本思路
• 算法框架
• 經(jīng)典例題

回溯算法的來(lái)源
首先，我們得明白啥叫回溯算法，它的由來(lái)是什么。

根據(jù)維基百科給出的定義👇

回溯算法也叫試探法，它是一種系統(tǒng)地搜索問(wèn)題的解的方法。

用回溯算法解決問(wèn)題的一般步驟：

1、 針對(duì)所給問(wèn)題，定義問(wèn)題的解空間，它至少包含問(wèn)題的一個(gè)（最優(yōu)）解。

2 、確定易于搜索的解空間結(jié)構(gòu),使得能用回溯法方便地搜索整個(gè)解空間 。

3 、以深度優(yōu)先的方式搜索解空間，并且在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索。

用更加簡(jiǎn)單的話術(shù)來(lái)解釋的話👇

回溯法可以理解成為通過(guò)選擇不同的岔路口，來(lái)尋找目的地，一個(gè)岔路口一個(gè)岔路口的去嘗試找到目的地，如果走錯(cuò)了路的話，繼續(xù)返回到上一個(gè)岔路口的另外一條路，直到找到目的地。

基本思路
首先，我們得明確這個(gè)回溯算法的思路是什么，有了思路，我們才可以根據(jù)這個(gè)思路寫(xiě)出偽代碼，有了偽代碼之后，根據(jù)實(shí)際的問(wèn)題，寫(xiě)出相應(yīng)的解決方案。

我們可以把這類(lèi)回溯問(wèn)題，看成是解決一個(gè)決策樹(shù)的遍歷過(guò)程，這樣子也方便我們接下來(lái)的解釋👇

基本思路：

• 從決策樹(shù)的一條路開(kāi)始走，能進(jìn)則進(jìn)，不能進(jìn)則退回來(lái)，換一條路試一試。

舉個(gè)例子來(lái)說(shuō)，還是拿八皇后問(wèn)題來(lái)解釋?zhuān)?/p>

• 第一步按照順利，也就是在第一行，我們放置第一個(gè)皇后。
• 第二步，我們需要在第二行放置一個(gè)皇后，我們需要遍歷，將符合要求的位置放置皇后。
• 第三步，也就是在第三行，我們需要去遍歷，找到符合的位置，如果都沒(méi)有符合要求，我們就需要「撤銷(xiāo)第二步操作」，那么需要改變第二個(gè)皇后位置，重新放置第二個(gè)皇后位置，直到滿足第三個(gè)皇后放置的位置。
• 當(dāng)你改變第二個(gè)皇后位置后，都無(wú)法滿足第三個(gè)皇后位置的時(shí)候，我們就需要「撤銷(xiāo)第一步操作」，重新去放置第一個(gè)皇后位置，然后按照順序完成后續(xù)操作。

我們可以通過(guò)另外一個(gè)例子來(lái)看，也就是回溯在迷宮搜索中也很常見(jiàn)，簡(jiǎn)單來(lái)說(shuō)，就是這條路走不通的話，我們就需要「撤銷(xiāo)上個(gè)操作」，返回前一個(gè)路口，繼續(xù)下一條路。

似乎你已經(jīng)發(fā)現(xiàn)了，回溯說(shuō)到底就是「窮舉法」，但是如果你只是單純的窮舉的話，不剪枝的話，時(shí)間復(fù)雜度是巨大的，那么如何剪枝呢？

我們將回溯優(yōu)化的方法可以稱(chēng)之為剪枝，或者是剪枝函數(shù)，通過(guò)這個(gè)函數(shù)，我們可以減去一些狀態(tài)，剪去一些不可能到達(dá)（「最終狀態(tài)」），這里說(shuō)的最終狀態(tài)，可以認(rèn)為是答案狀態(tài)，這樣子的話，就減少了部分空間樹(shù)節(jié)點(diǎn)的生成，具體如何剪枝的話，可以根據(jù)做題經(jīng)驗(yàn)多加練習(xí)，這里就不張開(kāi)了。

算法框架
其實(shí)刷了一定的題量，你會(huì)發(fā)現(xiàn)，對(duì)于這種回溯思路而言，都是有一定的套路的，那么接下來(lái)就給出偽代碼👇

接下來(lái)是自己的一點(diǎn)理解，覺(jué)得按照這個(gè)步驟來(lái)的話，也好理解一些👇

可以按照3個(gè)步驟來(lái)思考這類(lèi)的問(wèn)題：

1. 「路徑」：記錄做出的選擇。
2. 「選擇列表」：通常而言，用數(shù)組存儲(chǔ)可以選擇的操作。
3. 「結(jié)束條件」：一般而言，就是遞歸的結(jié)束點(diǎn)，也就是搜索的結(jié)束點(diǎn)。

result = [] 
 
function backtrack(路徑, 選擇列表) { 
    if('滿足結(jié)束條件') { 
        // 這里就是對(duì)答案做更新,依據(jù)實(shí)際題目出發(fā) 
        result.push(路徑) 
        return 
    } else { 
        for(let i = 0; i < 選擇列表.length; i++) { 
            // 對(duì)一個(gè)選擇列表做相應(yīng)的選擇 
             
            做選擇 
             
            backtrack(路徑, 選擇列表) 
             
            // 既然是回溯算法,那么在一次分岔路做完選擇后 
            // 需要回退我們之前做的操作 
             
            撤銷(xiāo)選擇 
        } 
    } 
} 

做過(guò)類(lèi)似的題目都知道，核心的處理就是for循環(huán)里面的遞歸操作，每次在遞歸之前，「做選擇」，在這種方案結(jié)束后，我們需要「撤銷(xiāo)選擇」，這樣子的話，就不會(huì)影響同一層決策樹(shù)的其他選擇。

舉個(gè)例子，在走迷宮這類(lèi)題型中，我們需要不斷的去搜索，去試探答案，這個(gè)過(guò)程就是一個(gè)回溯算法的過(guò)程，每次要走下一個(gè)格子的時(shí)候，我們需要先將這個(gè)格子「做個(gè)標(biāo)記」，代表這個(gè)格子已經(jīng)走過(guò)，然后在往后繼續(xù)搜索...

當(dāng)這個(gè)方案不合理的時(shí)候，我們是不是需要將之前標(biāo)記的格子清除標(biāo)記呢？仔細(xì)想一想的話，這樣子是非常合理的，在當(dāng)前方案行不通的時(shí)候，我們要將這個(gè)「步驟撤銷(xiāo)掉」。

對(duì)于以上的基礎(chǔ)知識(shí)，有了一定了解，接下來(lái)我們就通過(guò)這么基礎(chǔ)知識(shí)來(lái)解決問(wèn)題。

怎么樣寫(xiě)回溯
做一些題目后，對(duì)回溯算法有初步認(rèn)識(shí)后，我覺(jué)得可以參考下面的步驟來(lái)刻意練習(xí)👇

• 首先畫(huà)出遞歸樹(shù)，找到狀態(tài)變量（這里可以理解成回溯函數(shù)參數(shù)）。
• 確定遞歸出口，一般根據(jù)具體題目條件而言。
• 找準(zhǔn)選擇列表（一般而言與函數(shù)參數(shù)有關(guān)）。
• 剪枝，對(duì)于一些情況而言，可以適當(dāng)剪枝。
• 做出選擇，遞歸調(diào)用，進(jìn)入下一層。
• 撤銷(xiāo)選擇。

我覺(jué)得這個(gè)對(duì)回溯算法的總結(jié)，是挺不錯(cuò)的，可以借鑒下。

2個(gè)例子
接下來(lái)，我們通過(guò)三個(gè)題目作為例子，來(lái)看看怎么根據(jù)我們之前提及的算法框架來(lái)解決問(wèn)題👇

字母大小寫(xiě)全排列⭐
鏈接：字母大小寫(xiě)全排列

給定一個(gè)字符串S，通過(guò)將字符串S中的每個(gè)字母轉(zhuǎn)變大小寫(xiě)，我們可以獲得一個(gè)新的字符串。返回所有可能得到的字符串集合。

示例：

輸入：S = "a1b2" 輸出：["a1b2", "a1B2", "A1b2", "A1B2"]

輸入：S = "3z4" 輸出：["3z4", "3Z4"]

輸入：S = "12345" 輸出：["12345"]

提示：

S 的長(zhǎng)度不超過(guò)12。S 僅由數(shù)字和字母組成。

來(lái)源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/letter-case-permutation 著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

嗯，這題的話，可以通過(guò)畫(huà)圖舉個(gè)例子來(lái)說(shuō)，我這里就借鑒網(wǎng)上的圖了👇

字母全排列

對(duì)于數(shù)字而言的話，我們直接跳過(guò)，字母的話，無(wú)非就是兩種狀態(tài)，大小寫(xiě)字母，那么我們就有接下來(lái)的思路👇

• 遇到數(shù)字的話，不會(huì)涉及新的分支，我們就直接往后搜，這樣子的話，對(duì)于數(shù)字就只需要搜索一次。
• 對(duì)于單個(gè)字母而言，我們需要「搜索2次」，小寫(xiě)字母搜索一次，大寫(xiě)字母搜索一次。
• 我們可以去維護(hù)一個(gè)index，遇到數(shù)字的話，index+1，繼續(xù)遞歸，遇到字母的話，需要遞歸兩次，假設(shè)當(dāng)字母是小寫(xiě)時(shí)，我們遞歸一次(index+1),然后回溯時(shí)將字母轉(zhuǎn)為大寫(xiě)，又去遞歸一次。
• 遞歸盡頭：即搜索完整個(gè)字符串為止，我們前面維護(hù)的index，這個(gè)時(shí)候就可以作為條件判斷。

按照這個(gè)思路走的話，我們就可以寫(xiě)出完整的解題代碼

代碼👇

回溯算法代碼-1
 

代碼點(diǎn)這里☑️

子集🐍⭐⭐
鏈接：子集

給定一組不含重復(fù)元素的整數(shù)數(shù)組 nums，返回該數(shù)組所有可能的子集（冪集）。

說(shuō)明：解集不能包含重復(fù)的子集。

示例:

輸入: nums = [1,2,3] 輸出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

來(lái)源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/subsets 著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

做這類(lèi)題目的時(shí)候，不太懂的話，可以先畫(huà)圖，從上面的題來(lái)看，我們可以畫(huà)類(lèi)似一個(gè)樹(shù)的結(jié)構(gòu)，然后看看如何去遍歷這個(gè)決策樹(shù)，看看能不能剪枝，直接借鑒一下網(wǎng)上的圖👇

 子集的遞歸樹(shù)

其實(shí)把這個(gè)圖畫(huà)出來(lái)，你應(yīng)該就成功一半了，從這個(gè)圖來(lái)看，我們似乎又可以去遍歷這顆樹(shù)。

首先我們得把我們思路整理一下👇

• 這題肯定是求樹(shù)的所有節(jié)點(diǎn)！
• 對(duì)這顆樹(shù)而言，我們可以遍歷它的分支，選擇其中一個(gè)分支，然后繼續(xù)向下操作，不選這個(gè)分支的話，選擇另外一個(gè)分支又是另外一個(gè)情況，所以每次枚舉下一個(gè)數(shù)字的時(shí)候,也就是兩種選擇：選或不選。
• 可以考慮使用一個(gè)index指針來(lái)記錄「節(jié)點(diǎn)」的狀態(tài),即當(dāng)前遞歸考察的數(shù)字nums[index]
• 遞歸結(jié)束的條件：index === nums.length, 這個(gè)時(shí)候代表考察完所有的數(shù)字，把當(dāng)前的子集加入題解，結(jié)束當(dāng)前遞歸分支。
• 每次結(jié)束一個(gè)分支，即結(jié)束遞歸，需要撤銷(xiāo)當(dāng)前的選擇，（從list中刪除），回到選擇前的狀態(tài)，做另外一個(gè)選擇，即不選擇當(dāng)前的數(shù)字，往下遞歸，繼續(xù)生成子集。

根據(jù)以上的偽代碼，我們基本上就能解出這個(gè)題目👇

回溯算法題解-2
 

代碼點(diǎn)這里☑️

題目是做不完的，做完這些題目后，希望你能找出回溯算法的規(guī)律，能對(duì)它有更加深入的理解~，接下來(lái)準(zhǔn)備了些題集，希望對(duì)你們有幫助~

進(jìn)階題目匯總
以下是我在網(wǎng)上看到一套不錯(cuò)的回溯算法題集，如果你還在刻意找的話，可以看看這里。