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

输出

执行上述代码时，它会产生以下结果 -