回溯是递归的一种形式。 但它涉及选择任何可能性的唯一选择。我们从选择一个选项开始,并从中退出。如果达到一个状态,会得出这样的结论:这个特定的选项不能提供所需的解决方案。 通过遍历每个可用选项来重复这些步骤,直到获得所需的解决方案。
以下是查找给定字母集合的所有可能排列顺序的示例。 当选择一对时,我们应用回溯来验证是否已经创建了该确切的一对。 如果尚未创建,则将该对添加到答案列表中,否则将被忽略。
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']