Python回溯

回溯是遞迴的一種形式。 但它涉及選擇任何可能性的唯一選擇。我們從選擇一個選項開始，並從中退出。如果達到一個狀態，會得出這樣的結論:這個特定的選項不能提供所需的解決方案。 通過遍歷每個可用選項來重複這些步驟，直到獲得所需的解決方案。

以下是查詢給定字母集合的所有可能排列順序的範例。 當選擇一對時，我們應用回溯來驗證是否已經建立了該確切的一對。 如果尚未建立，則將該對新增到答案列表中，否則將被忽略。

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"]))

執行上面範例程式碼，得到以下結果 -

['a', 'b', 'c']
['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']