回溯算法详解：原理、代码与示例

回溯解决什么问题

有些问题要求给出满足一组规则的所有排布，或其中任意一种：放置 8 个皇后使它们互不攻击、填满数独、列出和为目标值的所有子集、找出把字符串拆成词典单词的所有方式。这类问题没有巧妙的公式，只能搜索。盲目尝试每一种完整组合太慢了，但大多数部分组合在做出几个选择之后就已经无效。

回溯会在每一次选择之后检查规则。一旦某个部分解违反规则，它就立刻放弃搜索树中的整个分支，退回去尝试下一个选项。

用大白话讲思路

1. 如果当前的部分解已经完整，就把它记录下来。
2. 否则，对每个可能的下一步选择：如果该选择是允许的，就做出它（选择）。
3. 递归地继续扩展解（探索）。
4. 撤销这个选择，使下一个选项从相同的状态出发（撤销）。

搜索空间是一棵树：根是空解，每一层增加一个选择，叶子是完整的候选解。回溯就是在这棵树上做深度优先搜索，而剪枝是指砍掉不可能包含解的子树。

实例：4 皇后

在 4 × 4 的棋盘上放置 4 个皇后，每行一个，要求任意两个皇后不在同一列或同一条对角线上。列编号为 0 到 3。

继续搜索会找到唯一的另一个解 2, 0, 3, 1，它是第一个解的镜像。

Python 实现

用集合记录已占用的列和对角线，使每次安全检查都是 O(1)。在一条对角线上 row - col 是常数，在另一条对角线上 row + col 是常数。

def solve_n_queens(n):
    solutions, cols = [], []
    used_cols, diag1, diag2 = set(), set(), set()

    def place(row):
        if row == n:
            solutions.append(cols.copy())   # copy, not the live list
            return
        for col in range(n):
            if col in used_cols or row - col in diag1 or row + col in diag2:
                continue                    # prune: square is attacked
            cols.append(col)                # choose
            used_cols.add(col); diag1.add(row - col); diag2.add(row + col)
            place(row + 1)                  # explore
            cols.pop()                      # unchoose
            used_cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)

    place(0)
    return solutions

print(solve_n_queens(4))       # [[1, 3, 0, 2], [2, 0, 3, 1]]
print(len(solve_n_queens(8)))  # 92

同样的模板可以生成所有子集和所有排列：

def subsets(items):
    result, current = [], []

    def go(i):
        if i == len(items):
            result.append(current.copy())
            return
        current.append(items[i]); go(i + 1); current.pop()   # take items[i]
        go(i + 1)                                            # skip items[i]

    go(0)
    return result

def permutations(items):
    result, current, used = [], [], [False] * len(items)

    def go():
        if len(current) == len(items):
            result.append(current.copy())
            return
        for i, x in enumerate(items):
            if not used[i]:
                used[i] = True; current.append(x)
                go()
                used[i] = False; current.pop()

    go()
    return result

print(subsets([1, 2, 3]))
# [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]
print(permutations([1, 2, 3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

在实际代码中，若只是求普通的子集和排列，itertools.combinations 和 itertools.permutations 更快。只有需要用问题特有的规则剪枝时，才自己写回溯。

时间与空间复杂度

回溯无法突破输出规模的下限：如果必须列出 n! 个排列，至少需要 n! 步。剪枝只能通过跳过不产生任何结果的分支来提高效率。

变体与常见错误

• 忘记撤销：递归调用之后如果没有恢复状态，之后的分支就会看到过时的选择。
• 追加了“活”的列表：result.append(current) 保存的是一个之后还会被修改的引用；应追加 current.copy()。
• 输入中有重复元素：先对元素排序，并在同一深度跳过与前一个相等的元素，以避免出现重复的子集或排列。
• 找到第一个解就停止：当一个解就足够时（如数独求解器），让递归返回 True 并终止循环。
• 更好的顺序：先尝试约束最多的选择（对数独来说，就是候选数最少的空格）。这通常能让搜索树大幅缩小。

何时使用及实际应用

• 约束满足问题：数独、填字游戏、地图着色、排课表和考试安排。
• SAT 求解器和 Prolog 式的逻辑引擎都建立在带强力剪枝的回溯搜索之上。
• 许多语言的正则表达式引擎（包括 Python 的 re）使用回溯；写得不好的模式可能发生指数级回溯（“灾难性回溯”）。
• 面试题：子集、全排列、组合总和、N 皇后、网格中的单词搜索、分割回文串、括号生成、电话号码的字母组合。