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