回溯是遞歸的一種形式。 但它涉及選擇任何可能性的唯一選擇。我們從選擇一個(gè)選項(xiàng)開始，并從中退出。如果達(dá)到一個(gè)狀態(tài)，會(huì)得出這樣的結(jié)論:這個(gè)特定的選項(xiàng)不能提供所需的解決方案。 通過遍歷每個(gè)可用選項(xiàng)來重復(fù)這些步驟，直到獲得所需的解決方案。
以下是查找給定字母集合的所有可能排列順序的示例。 當(dāng)選擇一對時(shí)，我們應(yīng)用回溯來驗(yàn)證是否已經(jīng)創(chuàng)建了該確切的一對。 如果尚未創(chuàng)建，則將該對添加到答案列表中，否則將被忽略。
def permute(list, s):
if list == 1:
return s
else:
return [ y + x
for y in permute(1, s)
for x in permute(list - 1, s)
]
print(permute(1, ["a","b","c"]))
print(permute(2, ["a","b","c"]))
執(zhí)行上面示例代碼，得到以下結(jié)果 -
['a', 'b', 'c']
['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']
掃碼關(guān)注鍍金池微信號
手機(jī)訂課，優(yōu)惠多多