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