回溯算法應(yīng)用場(chǎng)合

回溯算法和遞歸算法一般同時(shí)出現(xiàn)，一般遞歸算法的下面就是回溯的邏輯。
一般說遞歸函數(shù)，其實(shí)就是回溯函數(shù)。回溯一般不會(huì)單獨(dú)出現(xiàn)。
回溯法其實(shí)是一個(gè)純暴力的搜索算法。有些問題用for循環(huán)搜索不出來，必須用回溯算法。以下幾種問題必須用回溯。

• 組合問題。N個(gè)數(shù)里面按一定規(guī)則找出k個(gè)數(shù)的集合。如給定一個(gè)數(shù)組[1234]，從中找出大小為2的集合，結(jié)果是12,13,14,23,24,34
• 切割問題。一個(gè)字符串按一定規(guī)則有幾種切割方式。如給定一個(gè)字符串，求如何切割保證子串都是回文子串。
• 子集問題。一個(gè)N個(gè)數(shù)的集合里有多少符合條件的子集。如求出數(shù)組【1234】的子集，答案是1,2，3,4，12,13,14,23,24,34，123,124,234,1234。
• 排列問題。N個(gè)數(shù)按一定規(guī)則全排列，有幾種排列方式。如果一個(gè)是12，求它的排列，答案是12，21。。組合強(qiáng)調(diào)元素是什么，不關(guān)心順序，排列關(guān)心。
• 棋盤問題。如 N皇后，解數(shù)獨(dú)。

回溯算法的理解

回溯算法可以抽象成一個(gè)樹形結(jié)構(gòu)。
回溯算法前面有遞歸，遞歸都是有終止條件的。
回溯是遞歸的副產(chǎn)品，只要有遞歸就會(huì)有回溯」，所以回溯法也經(jīng)常和二叉樹遍歷，深度優(yōu)先搜索混在一起，因?yàn)檫@兩種方式都是用了遞歸。

如圖所示，樹的寬度表示集合的大小，一般用for循環(huán)遍歷，樹的深度是遞歸的深度。

回溯法的模板如下

void backtracking(參數(shù)) {if (終止條件) {存放結(jié)果;#收集葉子節(jié)點(diǎn)return;}for (選擇：本層集合中元素（樹中節(jié)點(diǎn)孩子的數(shù)量就是集合的大小）) {處理節(jié)點(diǎn);##如我們求數(shù)組【1234】的子集合，葉子節(jié)點(diǎn)有12，這里告訴12是如何來的。backtracking(路徑，選擇列表); // 遞歸回溯，撤銷處理結(jié)果##就是撤銷處理節(jié)點(diǎn) 這一步。。。如求數(shù)組【1234】的組合，如開先放進(jìn)了1，再放進(jìn)了2，得到12為我們想要的組合。再把2回溯出去得到1，加入3，得到13組合} }

回溯算法問題求解

1.組合問題

給定兩個(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],
]

原始解法：for循環(huán)，k為2.兩層for循環(huán)

n=4 results=[] for i in range(1,n+1):for j in range(i+1,n+1):result=str(i)+str(j)results.append(result)print(results)

如果n為100，k為50呢，那就50層for循環(huán)，是不是開始窒息。

回溯算法求解
上面我們說了「要解決 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)一步理解。
「我們?cè)陉P(guān)于回溯算法，你該了解這些！中說道回溯法解決的問題都可以抽象為樹形結(jié)構(gòu)（N叉樹），用樹形結(jié)構(gòu)來理解回溯就容易多了」。
那么我把組合問題抽象為如下樹形結(jié)構(gòu)：

可以看出這個(gè)棵樹，一開始集合是 1，2，3，4， 從左向右取數(shù)，取過的數(shù)，不在重復(fù)取。
第一次取1，集合變?yōu)?，3，4 ，因?yàn)閗為2，我們只需要再取一個(gè)數(shù)就可以了，分別取2，3，4，得到集合[1,2] [1,3] [1,4]，以此類推。
「每次從集合中選取元素，可選擇的范圍隨著選擇的進(jìn)行而收縮，調(diào)整可選擇的范圍」。
「圖中可以發(fā)現(xiàn)n相當(dāng)于樹的寬度，k相當(dāng)于樹的深度」。

那么如何在這個(gè)樹上遍歷，然后收集到我們要的結(jié)果集呢？

「圖中每次搜索到了葉子節(jié)點(diǎn)，我們就找到了一個(gè)結(jié)果」。

相當(dāng)于只需要把達(dá)到葉子節(jié)點(diǎn)的結(jié)果收集起來，就可以求得 n個(gè)數(shù)中k個(gè)數(shù)的組合集合。

解題步驟

第一步：這里要定義兩個(gè)全局變量，一個(gè)用來存放符合條件單一結(jié)果path，一個(gè)用來存放符合條件結(jié)果的集合result。

第二步:函數(shù)里一定有兩個(gè)參數(shù)，既然是集合n里面取k的數(shù)，那么n和k是兩個(gè)int型的參數(shù)。
然后還需要一個(gè)參數(shù)，為int型變量startIndex，這個(gè)參數(shù)用來記錄本層遞歸的中，集合從哪里開始遍歷（集合就是[1,…,n] ）。
為什么要有這個(gè)startIndex呢？
「每次從集合中選取元素，可選擇的范圍隨著選擇的進(jìn)行而收縮，調(diào)整可選擇的范圍，就是要靠startIndex」。
從，在集合[1,2,3,4]取1之后，下一層遞歸，就要在[2,3,4]中取數(shù)了，那么下一層遞歸如何知道從[2,3,4]中取數(shù)呢，靠的就是startIndex。

終止條件
path這個(gè)數(shù)組的大小如果達(dá)到k，說明我們找到了一個(gè)子集大小為k的組合了，

class Solution:def combine(self, n: int, k: int):result = []def recall(n, k, startindex, result, path):if len(path) == k:result.append(path[:])returnfor i in range(startindex, n+1):path.append(i)recall(n, k, i+1, result, path)path.pop()recall(n, k, 1, result, [])return resultc=Solution() d=c.combine(n=4,k=2) print(d)

2.分割問題

給定一個(gè)字符串 s，將 s 分割成一些子串，使每個(gè)子串都是回文串。
返回 s 所有可能的分割方案。
示例:
輸入: “aab”
輸出:
[
[“aa”,“b”],
[“a”,“a”,“b”]
]

class Solution:def partition(self, s: str):#判斷是否回文def helper(subStr):i, j = 0, len(subStr) - 1while i <= j:if subStr[i] != subStr[j]:return Falsei += 1j -= 1return Truedef recall(s, size, start, subset):if start == size:#如果遍歷完啦，結(jié)束res.append(subset[:])returnfor i in range(start, size):if not helper(s[start:i + 1]):continuesubset.append(s[start:i + 1])#中見間結(jié)果#print(subset)recall(s, size, i + 1, subset)subset.pop()res = []size = len(s)recall(s, size, 0, [])return resif __name__ == "__main__":s = "aab"split_result = Solution().partition(s)print(split_result)

3.子集問題

給定一組不含重復(fù)元素的整數(shù)數(shù)組 nums，返回該數(shù)組所有可能的子集（冪集）。
說明：解集不能包含重復(fù)的子集。
示例:
輸入: nums = [1,2,3]
輸出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

class Solution:def subsets(self, nums: List[int]) -> List[List[int]]:ans = []# 存儲(chǔ)符合要求的子集tmp = []n = len(nums)def helper(idx):# 先添加子集ans.append(tmp[:])for i in range(idx, n):tmp.append(nums[i])# 避免重復(fù)，每次遞歸，從下一個(gè)索引開始helper(i+1)# 回溯tmp.pop()helper(0,0)return ans

4.全排列問題

給定一個(gè) 沒有重復(fù) 數(shù)字的序列，返回其所有可能的全排列。
示例:
輸入: [1,2,3]
輸出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

class Solution:def permute(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""def backtrack(first = 0):# 所有數(shù)都填完了if first == n: res.append(nums[:])for i in range(first, n):# 動(dòng)態(tài)維護(hù)數(shù)組nums[first], nums[i] = nums[i], nums[first]# 繼續(xù)遞歸填下一個(gè)數(shù)backtrack(first + 1)# 撤銷操作nums[first], nums[i] = nums[i], nums[first]n = len(nums)res = []backtrack()return res

總結(jié)

以上是生活随笔為你收集整理的一篇带你搞透回溯算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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