引言

回溯算法實(shí)際上就是對(duì)樹形或者圖形結(jié)構(gòu)執(zhí)行一次深度優(yōu)先遍歷，實(shí)際上類似枚舉的搜索嘗試過(guò)程，在遍歷的過(guò)程中尋找問(wèn)題的解，深搜實(shí)際上就是遞歸的過(guò)程，所以我們得明白幾個(gè)前提：
1，回溯類的題目可以轉(zhuǎn)化為N叉樹去做（一般畫圖就有思路了）
2，回溯類的題目實(shí)際就是一種暴力的深搜；

回溯函數(shù)中的for循環(huán)和遞歸的作用

回溯算法都有個(gè)套路，就是寫一個(gè)回溯函數(shù)backtracking，一般格式就是：

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

這里的for循環(huán)套遞歸分別是什么意思？
for循環(huán)是橫向遍歷N叉樹
遞歸是縱向遍歷N叉樹

所以只有當(dāng)一縱列遞歸完了，for循環(huán)才會(huì)走到下一縱列；而且遞歸結(jié)果是逐漸從下往上來(lái)的；

問(wèn)題類型：子集問(wèn)題，組合問(wèn)題，分割問(wèn)題，排列問(wèn)題

子集問(wèn)題要求的其實(shí)就是樹的每一個(gè)節(jié)點(diǎn)，而組合和分割問(wèn)題都是求的葉子節(jié)點(diǎn)，排列問(wèn)題也是求葉子節(jié)點(diǎn)，但是和組合分割又有區(qū)別
子集問(wèn)題（入門）：78. 子集
組合問(wèn)題（入門）：77. 組合（回溯算法）
分割問(wèn)題（入門）：131. 分割回文串（回溯算法）
排列問(wèn)題（入門）：46.全排列

什么時(shí)候需要一個(gè)start變量作為for循環(huán)起點(diǎn)？

當(dāng)通過(guò)一個(gè)集合求組合（或分割或子集），需要start，防止重復(fù)；

for (int i = start; i < nums.size(); ++i)

題目：77. 組合（回溯算法）
當(dāng)通過(guò)多個(gè)集合求組合（或分割或子集），不需要start，因?yàn)楦鱾€(gè)集合都不同不會(huì)相互影響；

for (int i = 0; i < nums.size(); ++i)

題目：17. 電話號(hào)碼的字母組合（回溯算法）

如果是排列問(wèn)題的話，就不需要start，因?yàn)槊康叫碌囊涣卸夹枰匦率褂弥笆褂玫脑?#xff1b;

for (int i = 0; i < nums.size(); ++i)

如果有start，什么時(shí)候遞歸時(shí)i加1？

當(dāng)一個(gè)集合中每個(gè)元素只能使用一次時(shí)，i + 1；（例題代碼）

for (int i = start; i < nums.size(); ++i) {path.push_back(nums[i]);backtracking(nums, i + 1);//遞歸 i + 1path.pop_back();//回溯}

當(dāng)一個(gè)集合中每個(gè)元素可以重復(fù)使用時(shí)，不用加1；

for (int i = start; i < nums.size(); ++i) {path.push_back(nums[i]);backtracking(nums, i);//遞歸 i不用加1path.pop_back();//回溯}

例題：求組和數(shù)II

這里 i + 1 實(shí)際上就是在遞歸過(guò)程中縱向處理子串，使每向下走一層就減少一個(gè)之前使用過(guò)的元素，防止重復(fù)使用之前使用過(guò)的元素；（畫圖好理解，主要理解遞歸是縱向遍歷的就好理解了）

需要去重類的題目：“樹層去重”和“樹枝去重”

有的題目不讓結(jié)果出現(xiàn)重復(fù)的元素，所以需要一個(gè)去重操作；
一般是在backtracking函數(shù)參數(shù)中多加入一個(gè) vector<bool> used型的參數(shù)，記錄每個(gè)節(jié)點(diǎn)的使用情況
這里需要注意去重有兩種情況：
數(shù)層去重和樹枝去重
used[i] == true，說(shuō)明同一樹枝元素 i 使用過(guò)
used[i] == false，說(shuō)明同一樹層元素 i 使用過(guò)

在子集和組合的題目中的去重實(shí)際上要去重的是同一樹層 上的“使用過(guò)”，同一樹枝上的都是一個(gè)組合里的元素，不用去重

而在排列的題目中去重去兩種情況都可能出現(xiàn)，但是樹枝去重是必須的，樹層去重需要根據(jù)實(shí)際情況來(lái)判斷；
如題目：47. 全排列 就是兩種去重都有的；

這里說(shuō)明一下為什么是false，因?yàn)槿绻麨閒alse，說(shuō)明遞歸已經(jīng)結(jié)束，已經(jīng)通過(guò)回溯回到了false，所以此時(shí)該遍歷的是旁邊一層（即下一個(gè)樹枝，同一層）的元素，即右移一個(gè)；
如果是true，則說(shuō)明是這一個(gè)樹枝上已經(jīng)使用的元素，一般這里去重出現(xiàn)在排列中；

例題 90.子集||部分代碼（樹層去重）

for (int i = start; i < nums.size(); ++i) {//去重操作if (i > 0 && nums[i - 1] == nums[i] && used[i - 1] == false) {continue;}path.push_back(nums[i]);used[i] = true;backtacking(nums, i + 1, used);used[i] = false;path.pop_back();}

例題46.全排列部分代碼（樹枝去重）

for (int i = 0; i < nums.size(); ++i) {if (used[i] == true) continue;used[i] = true;path.push_back(nums[i]);backTracking(nums, used);path.pop_back();used[i] = false;}

樹層去重前要注意需要先給原集合進(jìn)行一個(gè)排序；
used初始化為false
例題：40.組合總和II

樹層去重的前提是要先對(duì)原集合進(jìn)行排序；
這里也有特殊情況：419.遞增子序列
這個(gè)題目就不能排序，可以看看解析；

補(bǔ)充：什么時(shí)候需要 樹層去重 什么時(shí)候需要 樹枝去重

1，如果一個(gè)集合里面會(huì)出現(xiàn)重復(fù)的元素，結(jié)果還不能有重復(fù)，那么就需要樹層去重
2，樹枝去重一般就會(huì)出現(xiàn)在排列問(wèn)題中，其他問(wèn)題暫時(shí)還沒(méi)有遇到

總結(jié)

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

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