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']