一道題目帶你搞懂回溯算法
明天就過年了，無論你有沒有回到家鄉(xiāng)，都祝你新的一年，有所收獲。
今天分享一道算法題，希望能讓你學(xué)會回溯算法的思路。
學(xué)會了回溯，你就能解決著名的八皇后問題，數(shù)學(xué)家高斯窮其一生都沒有解出八皇后的解，而借助現(xiàn)代計(jì)算機(jī)和回溯算法，你分分鐘就搞定了，當(dāng)然，N 皇后也不在話下。
回溯法（back tracking）是一種選優(yōu)搜素算法，又稱為試探法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。但當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，當(dāng)然，回溯也是暴力搜索法中的一種。
昨天看到一道回溯算法題目，非常燒腦，不過我很喜歡這種感覺，程序員應(yīng)該定期刷一刷算法題，只有刷算法題目的時(shí)候，我才覺得那是真正意義上的編程，平時(shí)的工作在多數(shù)情況下，都是熟練調(diào)用編程語言或框架的 API 而已。
這道題目是 leetcode 第 93 題，難度為中等，讓我們根據(jù)一個包含數(shù)字的字符串，復(fù)原它所有可能的 IP 地址。具體如下：
給定一個只包含數(shù)字的字符串，復(fù)原它并返回所有可能的 IP 地址格式。
有效的 IP 地址 正好由四個整數(shù)（每個整數(shù)位于 0 到 255 之間組成，且不能含有前導(dǎo) 0），整數(shù)之間用 '.' 分隔。
例如："0.1.2.201" 和 "192.168.1.1" 是有效的 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 是無效的 IP 地址。
示例 1：
輸入：s =?"25525511135"
輸出：["255.255.11.135","255.255.111.35"]
示例 2：
輸入：s =?"0000"
輸出：["0.0.0.0"]
示例 3：
輸入：s =?"1111"
輸出：["1.1.1.1"]
示例 4：
輸入：s =?"010010"
輸出：["0.10.0.10","0.100.1.0"]
示例 5：
輸入：s =?"101023"
輸出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/restore-ip-addresses
暴力窮舉
這個題目，我相信你大腦里最先想到的就是找三個點(diǎn)來分隔出 4 個字符串，然后判斷分隔出的 4 個字符串是否滿足 ip 某一段的要求，假如 4 個字符串都在 0 到 255 之間并且沒有前導(dǎo)的零，那就是一個合法的 ip 地址。
但是三個點(diǎn)號的位置不太容易窮舉，4 個字符串的長度倒是好窮舉的，每個字符串的長度至少是 1，至多是 3，只有 3 種可能，，因此可以窮盡 4 個字符串的所有長度，也就是 3 的 4 次方 81 種可能。
如果 4 個字符串的長度加起來等于給定字符串的長度時(shí)，就可以按長度分隔，然后分別進(jìn)行判斷了。能想到這一點(diǎn)，就不難寫出如下代碼：
class?Solution(object):
????def?restoreIpAddresses(self,?s):
????????"""
????????:type?s:?str
????????:rtype:?List[str]
????????"""
????????result?=?[]
????????for?a?in?range(1,4):
????????????for?b?in?range(1,4):
????????????????for?c?in?range(1,4):
????????????????????for?d?in?range(1,4):
????????????????????????if?a+b+c+d?==?len(s):
????????????????????????????s1?=?s[0:a]
????????????????????????????s2?=?s[a:a+b]
????????????????????????????s3?=?s[a+b:a+b+c]
????????????????????????????s4?=?s[-d:]
????????????????????????????if?self.isValid(s1)?\
????????????????????????????and?self.isValid(s2)?\
????????????????????????????and?self.isValid(s3)?\
????????????????????????????and?self.isValid(s4):
????????????????????????????????result.append("{}.{}.{}.{}".format(s1,s2,s3,s4))
????????return?result;
????????????????????????????
????def?isValid(self,s_sub):
????????if?len(s_sub)?>?1?and?s_sub.startswith('0'):
????????????return?False
????????if?int(s_sub)?<=?255:?#全部都由數(shù)字組成
????????????return?True
????????return?False
但這種方法非常易懂，但是卻不夠通用，無法舉一反三，比如說題目改成 ipv6 的地址，這種方法就不太合適了。
回溯思想
接下來我們嘗試一下回溯的思路。
比如 25525511135，先來確定 ip 的第一段，第一段最多有 3 種可能：2，25，255，這里可以使用一個小循環(huán)。假如先選擇 2 做為 ip 的第一段，2 小于等于 255，滿足要求。
接下來確定 ip 的第二段，也就是說對剩余的字符串 5525511135 重復(fù)上述操作，同樣的，最多有 3 種可能：5，55，525。假如這里選擇 5， 5 是小于等于 255 的，因此滿足條件。
接下來確定 ip 的第三段。
接下來確定 ip 的第四段。
每一段的選擇，都是同樣的操作。這就很像是一個決策樹，每做一次選擇，都是沿著樹的某一分支走到葉子節(jié)點(diǎn)的過程，我這里使用腦圖來展示一下這個決策樹。
上圖中除了葉子節(jié)點(diǎn)，其他節(jié)點(diǎn)都是 3 個子節(jié)點(diǎn)，某些我沒有畫出，希望不影響你理解。
每一層的檢索都是一個遞歸操作，遞歸的退出條件就是到第 5 層結(jié)束，第 5 層結(jié)束后如果沒有剩余字符串，說明找到了一個正確的 IP 地址，保存到結(jié)果集里即可。
不可避免地需要遍歷這棵決策樹的每個節(jié)點(diǎn)，比如 2.5.5.2,本質(zhì)就是多叉樹的遍歷操作，這也就是回溯思想的核心。寫代碼時(shí)我們可以把多叉樹的遍歷骨架寫出來：
def?backtrace(root?:str)?->?None:
????"""
????有 3 個子節(jié)點(diǎn)的多叉樹的中序遍歷。
????"""
????if?滿足退出條件：
????????if?滿足要求：
????????????加入結(jié)果集
????????退出
????for?i?in?range(0,3):
????????if?i?#索引不能超過字符串的長度
????????????#選擇?root[0:i+1]
????????????#具體做法就是?tmp_list.append(root[0:i+1])
????????????backtrace(root[i+1:])
????????????#撤銷選擇?root[0:i+1]?
????????????#具體做法就是?tmp_list.pop()
進(jìn)入下一輪決策（遞歸）之前，先做選擇，把當(dāng)前 ip 段加入路徑 tmp_list 中，決策（遞歸）完成后，再撤銷選擇。
這里有人可能不太理解，為什么需要撤銷選擇？其實(shí)不難理解，看上圖決策樹的最左邊的分支，當(dāng)遍歷到 2.5.5.2 發(fā)現(xiàn)不合適的時(shí)候，需要回溯到 2.5.5，然后選擇 25，也就是說最后的 2 加入 tmp_list 之后，判斷不合適，遞歸返回之后，我們需要把 2 刪除，然后騰出空間放 25，這也是為什么叫回溯算法的原因，遇到不符合目標(biāo)的，就回頭重新選擇。當(dāng)然了，遇到合適的，也要重新選擇，是因?yàn)槲覀円x出所有合法的 ip 地址。
接下來，為這個骨架填充一點(diǎn)血肉。遍歷了每個節(jié)點(diǎn)，需要把這些節(jié)點(diǎn)的順序保存下來，這里使用一個 tmp_list 來保存，為了編寫退出條件，還需要一個變量指示現(xiàn)在是第幾層，為了返回最終結(jié)果，再傳入一個 result 的數(shù)組來保存。
def?backtrace(root?:str,?tmp_list:list,?levle:?int,?result:list?)?->?None:
????"""
????有 3 個子節(jié)點(diǎn)的多叉樹的中序遍歷。
????tmp_list?保存遍歷的路徑，比如?2.5.5.2
????level?表示現(xiàn)在是第幾層，初始調(diào)用時(shí)傳入?1
????"""
????##剩余字符串為空，或者遍歷到第 5 層，終止遞歸。
????if?len(root)?==?0?or?level?==?5:
????????##同時(shí)滿足時(shí)，說明已經(jīng)找到了合法的ip
????????if?len(root)?==?0?and?level?==?5:
???????????result.append(".".join(tmp_list))?
????????return?
????for?i?in?range(0,3):
????????if?i?#索引不能超過字符串的長度
????????????#選擇?root[0:i+1]
????????????part?=?root[0:i+1]
????????????if?isValid(part):
????????????????#合法的部分，才去遞歸
????????????????#加入選擇
????????????????tmp_list.append(part)
????????????????backtrace(root[i+1:],tmp_list,level+1,result)
????????????????#撤銷選擇
????????????????tmp_list.pop()
????????????else:
????????????????pass
組裝一下，以下是完整代碼，可直接在 leetcode 運(yùn)行的，提交后看看結(jié)果：
class?Solution(object):
????def?restoreIpAddresses(self,?s):
????????"""
????????:type?s:?str
????????:rtype:?List[str]
????????"""
????????if?len(s)?4:
????????????return?[]
????????result?=?[]
????????tmp_list?=?[]
????????self.backtrace(s,tmp_list,1,result);
????????return?result
????def?backtrace(self,?root:str?,?tmp_list:list,?level:int,?result:list)?->?None:
????????"""
????????有 3 個子節(jié)點(diǎn)的多叉樹的中序遍歷。
????????tmp_list?保存遍歷的路徑，比如?2.5.5.2
????????level?表示現(xiàn)在是第幾層，初始調(diào)用時(shí)傳入?1
????????"""
????????if?len(root)?==?0?or?level?==?5:
????????????if?len(root)?==?0?and?level?==?5:
????????????????result.append(".".join(tmp_list))?
????????????return?
????????for?i?in?range(0,3):
????????????if?i?#索引不能超過字符串的長度
????????????????#選擇?root[0:i+1]
????????????????part?=?root[0:i+1]
????????????????if?self.isValid(part):
????????????????????#合法的部分，才去遞歸
????????????????????#加入選擇
????????????????????tmp_list.append(part)
????????????????????self.backtrace(root[i+1:],tmp_list,level+1,result)
????????????????????#撤銷選擇
????????????????????tmp_list.pop()
????????????????else:
????????????????????pass
????
????def?isValid(self,?sub_s?:?str)?->?bool:
????????if?len(sub_s)?>?1?and?sub_s.startswith('0'):
????????????return?False
????????if?0?<=?int(sub_s)?<=?255:
????????????return?True
????????return?False
運(yùn)行結(jié)果如下：
心心苦苦搞了半天，看來還沒有第一段暴力解法來得快，別灰心，一定有什么可以優(yōu)化的地方，其實(shí)，只要有某一段 ip 的長度大于 1，且是 0 開頭的時(shí)候，后面就不需要向下遞歸了，可以提升點(diǎn)效率。
比如：輸入：s = "010010"，當(dāng) "01"做為第一段時(shí)就可以 break 跳出循環(huán)了。
優(yōu)化一下 backtrace 函數(shù)和 isValid 函數(shù)：
????def?backtrace(self,?root:str?,?tmp_list:list,?level:int,?result:list)?->?None:
????????"""
????????有 3 個子節(jié)點(diǎn)的多叉樹的中序遍歷。
????????tmp_list?保存遍歷的路徑，比如?2.5.5.2
????????level?表示現(xiàn)在是第幾層，初始調(diào)用時(shí)傳入?1
????????"""
????????if?len(root)?==?0?or?level?==?5:
????????????if?len(root)?==?0?and?level?==?5:
????????????????result.append(".".join(tmp_list))?
????????????return?
????????for?i?in?range(0,3):
????????????if?i?#索引不能超過字符串的長度
????????????????#選擇?root[0:i+1]
????????????????part?=?root[0:i+1]
????????????????##如果某段以0開頭，且長度超過?1?，那么跳出循環(huán)，提升效率
????????????????if?part.startswith('0')?and?len(part)>1:
????????????????????break;
????????????????if?self.isValid(part):
????????????????????#合法的部分，才去遞歸
????????????????????#加入選擇
????????????????????tmp_list.append(part)
????????????????????self.backtrace(root[i+1:],tmp_list,level+1,result)
????????????????????#撤銷選擇
????????????????????tmp_list.pop()
????????????????else:
????????????????????pass
????
????def?isValid(self,?sub_s?:?str)?->?bool:
????????#?if?len(sub_s)?>?1?and?sub_s.startswith('0'):
????????#?????return?False
????????if?int(sub_s)?<=?255:
????????????return?True
????????return?False
一個小小的優(yōu)化，再次提交看結(jié)果，確實(shí)提升了不少：
由于 leetcode 同時(shí)有很多人使用，因此不同的時(shí)間提交，服務(wù)器的計(jì)算壓力是不同的，得出的結(jié)果會有少量的差異，這個理解就好。
到這里不知道你是否理解了回溯算法的思路。如果有不理解的地方，請?jiān)谖哪┝粞越涣鳌?/p>
最后的話
其實(shí)不管多么復(fù)雜的算法，歸根結(jié)底都逃離不開最基本的循環(huán)語句、if、else 的組合，再高級一點(diǎn)的，就是與棧、隊(duì)列、遞歸的組合應(yīng)用。
本文提到的回溯算法，本質(zhì)就是暴力遍歷多叉樹（本題是 3 叉樹）求解，先確定決策樹，寫出多叉樹的遍歷框架，然后填充內(nèi)容。不要忘記在遞歸完成后撤銷選擇。如果還有點(diǎn)不理解，這里我提個問題：
請問二叉樹前、中、后序遍歷的區(qū)別是什么，你可能會說不就是訪問根節(jié)點(diǎn)的順序不同么，先訪問根節(jié)點(diǎn)就是前序遍歷....
其實(shí)這樣的回答是錯的，無論哪一種遍歷，都是要先訪問根節(jié)點(diǎn)的，不訪問根節(jié)點(diǎn)，你怎么可能訪問得到子節(jié)點(diǎn)？
真正的區(qū)別在于對根節(jié)點(diǎn)的處理是放在進(jìn)入子節(jié)點(diǎn)的遞歸調(diào)用之前，還是在遞歸調(diào)用之后。前序遍歷的代碼在進(jìn)?某?個節(jié)點(diǎn)之前的那個時(shí)間點(diǎn)執(zhí)?，后序遍歷代碼在離開某個節(jié)點(diǎn)之后的那個時(shí)間點(diǎn)執(zhí)?，如下圖所示：
def?trace(root):
????##前序
????trace(root.left)
????##中序
????trace(root.right)
????##后序
因此后序遍歷之后，需要撤銷選擇的 child，加入新的 child 進(jìn)行遍歷。
PS：如果你也在刷 Leetcode，我這里有一份從 Leetcode 中精選大概 200 左右的題目，去除了某些繁雜但是沒有多少算法思想的題目，同時(shí)保留了面試中經(jīng)常被問到的經(jīng)典題目，對本號發(fā)消息回復(fù)「算法」即可獲取，讓你更高效地刷力扣。
如果覺得本文對你有用，請點(diǎn)贊在看轉(zhuǎn)發(fā)支持，感謝老鐵。