回溯算法

回溯算法

回溯法也可以叫做回溯搜索法，它是⼀种搜索的⽅式。 在⼆叉树系列中，我们已经不⽌⼀次，提到了回溯，例如⼆叉树：以为使⽤了递归，其实还隐藏着回溯。 回溯是递归的副产品，只要有递归就会有回溯。
回溯法解决的问题都可以抽象为树形结构，是的，我指的是所有回溯法的问题都可以抽象为树形结构！ 因为回溯法解决的都是在集合中递归查找⼦集，集合的⼤⼩就构成了树的宽度，递归的深度，都构成的 树的深度。 递归就要有终⽌条件，所以必然是⼀颗⾼度有限的树（N叉树）

回溯算法的基本模板：

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择