Python Data Structure 简明教程

Python - Backtracking

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

Backtracking is a form of recursion. But it involves choosing only option out of any possibilities. We begin by choosing an option and backtrack from it, if we reach a state where we conclude that this specific option does not give the required solution. We repeat these steps by going across each available option until we get the desired solution.

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

Below is an example of finding all possible order of arrangements of a given set of letters. When we choose a pair we apply backtracking to verify if that exact pair has already been created or not. If not already created, the pair is added to the answer list else it is ignored.

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

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

When the above code is executed, it produces the following result −

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