Python - 回溯_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']

<< Python - 分治算法 Python - 排序算法 >>