回溯算法（backtracking algorithm）是一种通过穷举来解决问题的办法，其本质是一种暴力搜索算法。它的核心思想是从一个初始状态出发，暴力搜索所有可能遇到的解决方案，当遇到正确的解则将其记录，直到找到解或尝试了所有可能的选择都无法找到解为止。

框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def backtrack(state: State, choices: list[choice], res: list[state]):
    """回溯算法框架"""
    # 判断是否为解
    if is_solution(state):
        # 记录解
        record_solution(state, res)
        # 不再继续搜索
        return
    # 遍历所有选择
    for choice in choices:
        # 剪枝：判断选择是否合法
        if is_valid(state, choice):
            # 尝试：做出选择，更新状态
            make_choice(state, choice)
            backtrack(state, choices, res)
            # 回退：撤销选择，恢复到之前的状态
            undo_choice(state, choice)

也可以简易描述为下面的框架：

1
2
3
4
5
6
7
8
9
def backtracking(参数):
    if 终止条件:
        存放结果
        return

    for 当前节点下的所有选择:
        处理节点，即做出该选择后更新后的状态，也就是更新路径
        backtracking(参数)
        回溯，撤销选择，恢复到之前的状态