backtracking

回溯是递归的一种形式。 但它涉及只选择任何可能性的选项。 我们首先选择一个选项并从中回溯，如果我们达到一个状态，我们得出这个特定选项不能提供所需解决方案的结论。 我们通过遍历每个可用选项重复这些步骤，直到我们得到所需的解决方案。

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

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