Python Data Structure 简明教程

Python - Backtracking

回溯是一种递归形式。但它仅涉及从任何可能中选择一个选项。我们首先选择一个选项，然后从中进行回溯，如果我们达到一个得出此特定选项无法给出所需解决方案的状态。我们通过遍历每个可用选项来重复这些步骤，直到找到所需解决方案。

下面是查找给定一组字母的所有可能排列顺序的示例。当我们选择一对时，我们会应用回溯来验证是否已经创建了该准确对。如果尚未创建，则将对添加到答案列表中，否则将忽略。

Example

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

Output

执行上述代码后，将生成以下结果 −

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