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']