♻️ 回溯法

回溯实际上就是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现不满足求解条件时，就回溯返回，尝试新的路径。

回溯的整体思路是：搜索每一条路，每次回溯是对具体一条路径而言的。对当前搜索路径下的未探索区域进行搜索，可能有两种情况：

1. 当前未搜索区域满足结束条件，保存当前路径并退出当前搜索
2. 当前未搜索区域需要继续搜索，则遍历当前所有可能的选择，如果选择符合要求，就把当前选择加入当前搜索路径中，并继续搜索新的未探索区域

回溯法模板如下：

res = []
path = []
def backtrack(未探索区域, res, path):
    if 未探索区域满足结束条件:
        res.add(path) # 深度拷贝
        return
    for 选择 in 未探索区域当前可能的选择:
        if 当前选择符合要求:
            path.add(当前选择)
            backtrack(新的未探索区域, res, path)
            path.pop()

backtrack的含义是：未探索区域中到达结束条件的所有可能路径，path 变量是保存的是一条路径，res变量保存的是所有搜索到的路径。所以当「未探索区域满足结束条件」时，需要把 path 放到结果 res 中。因为从始至终只用了一个变量 path，所以当对 path 增加一个选择并 backtrack 之后，需要清除当前的选择，path.pop()防止影响其他路径的搜索。