回溯算法在數(shù)據(jù)結(jié)構(gòu)中是一種常用的算法，也是一種暴力求解法，基本思想是深度遍歷，選擇一條路一步一步走，當(dāng)走不通的時(shí)候或者已經(jīng)求得正確的結(jié)果，返回上一步，接著選擇另一條路走，直到遍歷完所有節(jié)點(diǎn)。

回溯算法是一種思想，真正用代碼實(shí)現(xiàn)的時(shí)候，大多時(shí)候都需要用的方法是遞歸。

一. 回溯算法最出名的是8皇后問題，8皇后問題是在8*8格的棋盤上擺放8個(gè)皇后，使得這個(gè)8個(gè)皇后不在同一行上，也不在不一列上，也不在同一個(gè)對角線上，問有多少種擺法？

這個(gè)問題的解法是典型的回溯算法：

在第一行的某一個(gè)位置放置一個(gè)皇后，當(dāng)然是從第一個(gè)位置開始。

接著在第二行的找一個(gè)可以擺放皇后的位置，條件就是不在同一行，不在不一列也不在同一斜線上，如果找到則進(jìn)行下一行的查找，如果找不到，則回退到第一行的位置重新查找第一個(gè)皇后的位置，依次類推，直到8個(gè) 皇后都放到棋盤上。
代碼入下：

上面的代碼最主要的方法是recursionQueen，recursion是遞歸的意思，想象一下8*8的棋盤，參數(shù)row為0，從第一行開始，第一行的第一個(gè)位置符合條件，放置一個(gè)皇后，接著遞歸調(diào)用recursionQueen，row參數(shù)為1代表第二行，第二行的第一列檢查不符合條件，因?yàn)槲挥谕涣?#xff0c;接著看第二列，同樣不符合條件，接著看看第三列，符合條件，接著在遞歸調(diào)用recursionQueen，row為2表示第三行，放置第三個(gè)皇后，一次類推，直到第八行，第8個(gè)皇后符合條件之后，這就找出了第一種正確的擺放位置。

刪除最后一個(gè)皇后，在第8行接著找，直到遍歷完第8行找到全部的擺放位置。第8行遍歷完之后，也就走完了for循環(huán)，刪除第7行存在列表中皇后，在第七行接著尋找下一個(gè)符條件的皇后，找到之后接著在遞歸調(diào)用recursionQueen這個(gè)方法，尋找第8行符合條件的皇后。等到第7行遍歷完了之后接著刪除第六行的皇后，接著第六行遍歷，尋找第六行下一個(gè)符合條件的皇后，一次類推即可。
以上就是8皇后問題，寫的有點(diǎn)繞，多讀幾遍總能讀懂。
在做幾個(gè)回溯問題，鞏固一下：

二. 看下LeetCode中的 17. 電話號碼的字母組合這個(gè)問題，問題描述如下：

給定一個(gè)僅包含數(shù)字 2-9 的字符串，返回所有它能表示的字母組合。
給出數(shù)字到字母的映射如下（與電話按鍵相同）。注意 1 不對應(yīng)任何字母。

輸入："23"

輸出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

這個(gè)問題的解法和8皇后問題類似，比如輸入為23的時(shí)候，2中的所有字母代表一行，3中的所有字母代表第二行，那么就可以一次遞歸調(diào)用某一行的字母進(jìn)行組合，代碼入下：

上面的代碼也不是很難理解，每一個(gè)數(shù)字代表幾個(gè)字母，用其中的字母來進(jìn)行循環(huán)組合，一次遞歸調(diào)用，當(dāng)組合的長度和給的digits長度一致的時(shí)候，說明這次組合成功，并刪除最后一個(gè)字母，接著循環(huán)，尋找下一個(gè)符合條件的字母。

三. 在看一個(gè)LeetCode中37. 解數(shù)獨(dú) ：
編寫一個(gè)程序，通過已填充的空格來解決數(shù)獨(dú)問題。

一個(gè)數(shù)獨(dú)的解法需遵循如下規(guī)則：

數(shù)字 1-9 在每一行只能出現(xiàn)一次。
數(shù)字 1-9 在每一列只能出現(xiàn)一次。
數(shù)字 1-9 在每一個(gè)以粗實(shí)線分隔的 3x3 宮內(nèi)只能出現(xiàn)一次。
空白格用 '.' 表示。

代碼入下：

遍歷二維數(shù)組，當(dāng)遇到點(diǎn)的時(shí)候，從1到9開始嘗試，判斷是不是滿足條件，如果滿足，用當(dāng)前的數(shù)字替換點(diǎn)，

遞歸調(diào)用，因?yàn)樯弦粋€(gè)點(diǎn)已經(jīng)被替換了，接著遍歷二維數(shù)組，尋找下一個(gè)是的點(diǎn)的位置，找到之后在遍歷1到9查找符合條件的字符，找到之后接著再遞歸，還是走2

如果遍歷完了一到9，還是沒有符合條件的，則返回false，證明此路不通，開始回溯，把已經(jīng)負(fù)責(zé)的數(shù)字用點(diǎn)還原回去，在接著從1到9中尋找合適的數(shù)字

如此遞歸回溯，直到找到合適的為止。

四。 再看一個(gè)39. 組合總和
給定一個(gè)無重復(fù)元素的數(shù)組 candidates 和一個(gè)目標(biāo)數(shù) target ，找出 candidates 中所有可以使數(shù)字和為 target 的組合。

candidates 中的數(shù)字可以無限制重復(fù)被選取。

說明：

所有數(shù)字（包括 target）都是正整數(shù)。
解集不能包含重復(fù)的組合。
示例 1:

輸入: candidates = [2,3,6,7], target = 7,
所求解集為:
[
[7],
[2,2,3]
]
示例 2:

輸入: candidates = [2,3,5], target = 8,
所求解集為:
[
[2,2,2,2],
[2,3,3],
[3,5]
]

這道題目用回溯算法也很簡單，思想是從第一個(gè)元素開始，如果比目標(biāo)值小加到列表中，遞歸遍歷，并把目標(biāo)值和第一個(gè)元素的差值，還有開始遍歷的起始位置傳遞過去，

從起始位置開始遍歷，和目標(biāo)值比較，

如果和目標(biāo)值相等，找到對應(yīng)的素組，然后刪除列表的最后一個(gè)元素，接著遍歷

如果比目標(biāo)值大的話，忽略，繼續(xù)遍歷

當(dāng)一次循環(huán)做完，刪除上一次遞歸插入的元素值
代碼入下：

上面的代碼可以排序也可以不排序。 如果傳值start，每次遞歸調(diào)用都加1的話就成了不重復(fù)的元素了。

回溯算法看這幾個(gè)例子就差不多了吧。還想刷題鞏固的話 可以看LeetCode上面搜索關(guān)于回溯的題練習(xí)。

再小的努力，乘以365天也會變的偉大！歡迎關(guān)注我的公眾號 ：北風(fēng)中獨(dú)行的蝸牛

總結(jié)

以上是生活随笔為你收集整理的回溯法基本思想_数据结构之简单的回溯算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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