遇到"列出所有可能性"的题——所有排列、所有子集、N 皇后所有摆法——暴力枚举是不可能的,可能性太多了。这时候该回溯出场了:它像走迷宫,走不通就退回来换条路。这篇文章给你一套万能模板,并用四道经典题把它焊进脑子里。

1. 回溯的本质:做选择,然后撤销

回溯算法本质是带撤销的深度优先搜索。想象一棵决策树:每个节点是一个"选择",从根走到叶子就是一条完整结果。回溯就是先沿着一条路走到黑,发现到头了就退回到上一个岔路口(这一步叫"撤销"),换一条路再走。它保证不重不漏地探索所有可能,代价是时间可能是指数级的。

所有回溯题都长一个样,记住这个骨架:

def backtrack(path, choices):
    if 满足结束条件:
        results.append(path[:])   # 记录结果,注意深拷贝
        return
    for c in choices:
        path.append(c)            # 做选择
        backtrack(path, 更新后的choices)
        path.pop()                # 撤销选择,回到岔路口

三个关键点:结束条件决定什么时候记录结果;做选择把当前选择加入路径;撤销保证同一层循环里,每次尝试都从同样的状态出发。漏掉撤销,结果会互相污染,这是回溯最常见的 bug。

2. 全排列

给一个不含重复数字的数组,返回所有排列。排列关心顺序,所以同一个数字只能用一次,需要一个 used 数组标记哪些数字已经用过。路径长度达到 n 就是一条完整排列。

def permute(nums):
    res = []
    n = len(nums)

    def dfs(path, used):
        if len(path) == n:          # 结束条件:选满 n 个
            res.append(path[:])     # 深拷贝!直接 append(path) 会出错
            return
        for i, x in enumerate(nums):
            if used[i]:
                continue
            used[i] = True
            path.append(x)
            dfs(path, used)
            path.pop()              # 撤销
            used[i] = False         # 撤销标记

    dfs([], [False] * n)
    return res

for p in permute([1, 2, 3]):
    print(p)
# [1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]

为什么 res.append(path[:]) 而不是 res.append(path)?因为 path 是同一个列表对象,后续的 pop 会把它改掉;用切片 path[:] 生成一个副本,记录下来的结果才不会"变质"。这个坑几乎所有初学者都踩过。

复杂度也值得记住:全排列一共有 n! 个结果,每次记录要拷贝 O(n) 长度,所以总时间是 O(n · n!)。面试官问起来能立刻答出,说明你是真的理解了,而不是背的模板。

3. 子集:用起点控制顺序

子集不关心顺序,{1, 2} 和 {2, 1} 是同一个子集。为了避免重复,我们用起点下标控制:每一层只能从 start 开始往后选,这样生成的自然是有序的。另一个区别:全排列是"满了才记录",子集是"每一个中间状态都是结果",所以进入函数就先记录。

def subsets(nums):
    res = []

    def dfs(start, path):
        res.append(path[:])         # 当前路径就是一个子集
        for i in range(start, len(nums)):
            path.append(nums[i])
            dfs(i + 1, path)        # 只能选 i 后面的数
            path.pop()

    dfs(0, [])
    return res

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

对照全排列:排列用 used 防重,子集用 start 防重。原因:排列里 1 可以出现在任何位置,子集里元素之间的相对顺序是固定的。start 这个参数是回溯题的第二大考点,理解它,组合、分割、棋盘类问题就都通了。

子集这题还有一种等价写法:"每个元素选或不选"的二叉递归——不选就走 dfs(i + 1, path),选就走 dfs(i + 1, path + [nums[i]]),同样能枚举全部子集。两种写法都建议写一遍,能加深对"分支"的理解。

4. 组合:从 n 里选 k 个

组合和子集几乎一样,只是多了个长度限制:选满 k 个就记录并返回。比如从 1..n 里选 2 个,输出 [1,2] [1,3] [1,4] [2,3] [2,4] [3,4]。它还有个经典的剪枝优化:如果剩下的数已经不够凑满 k 个,直接结束这一层。

def combine(n, k):
    res = []

    def dfs(start, path):
        if len(path) == k:
            res.append(path[:])
            return
        # 剪枝:就算把 i..n 全选上也凑不满 k 个,就停
        for i in range(start, n + 1):
            if len(path) + (n - i + 1) < k:
                break
            path.append(i)
            dfs(i + 1, path)
            path.pop()

    dfs(1, [])
    return res

print(combine(4, 2))
# [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

剪枝不改变结果,只砍掉注定走不到终点的分支,让程序快很多。回溯的优化基本就两类:一类是这种"剩余不够"的可行性剪枝,另一类是后面要讲的去重剪枝。面试时主动提一句剪枝,是很加分的。

5. N 皇后:用集合做三维剪枝

N 皇后是回溯的巅峰入门题:在 n x n 棋盘放 n 个皇后,任意两个不能同行、同列、同对角线。逐行放皇后,天然解决了"同行";再用三个集合记录"被占用的列、主对角线、副对角线"。关键洞察:同一主对角线上 row - col 相等,同一副对角线上 row + col 相等。

def solve_n_queens(n):
    res = []
    board = [['.'] * n for _ in range(n)]
    cols = set()
    diag1 = set()   # row - col:主对角线
    diag2 = set()   # row + col:副对角线

    def dfs(row):
        if row == n:
            res.append([''.join(r) for r in board])
            return
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue          # 被攻击,跳过
            board[row][col] = 'Q'
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            dfs(row + 1)
            board[row][col] = '.'   # 撤销
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)

    dfs(0)
    return res

for b in solve_n_queens(4):
    print('\n'.join(b))
    print()
# .Q..  ...Q  Q...  ..Q.
# ...Q  Q...  ..Q.  .Q..
# Q...  ..Q.  ...Q  ..Q.
# ..Q.  .Q..  .Q..  Q...

用集合判冲突是 O(1) 的,比每次扫描棋盘优雅得多。注意撤销的顺序要和"做选择"完全对称:放皇后、加三个集合,撤回时就删皇后、减三个集合。不对称的撤销是回溯的第二大 bug 来源。

6. 进阶:有重复元素时的去重剪枝

如果输入数组里有重复数字,比如 [1, 2, 2],朴素回溯会产出重复子集。去重套路:先排序,让相同数字相邻;在同一层循环里,如果当前数字和上一个相同,就跳过——因为"以这个数字开头"的情况已经被上一个处理过了。

def subsets_with_dup(nums):
    nums.sort()          # 排序是去重的前提
    res = []

    def dfs(start, path):
        res.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue          # 同一层去重
            path.append(nums[i])
            dfs(i + 1, path)
            path.pop()

    dfs(0, [])
    return res

print(subsets_with_dup([1, 2, 2]))
# [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]

注意条件是 i > start 而不是 i > 0:前者只禁止"同一层"的重复选择,后者会误伤"不同层"的合法重复(比如 [2, 2] 里第二个 2 是合法的)。这个细节值得反复体会,也是全排列去重版(LeetCode 47)的核心。

7. 总结与练习

回溯的完整心法:画一棵决策树,明确"每一层选什么、结束条件是什么、怎么撤销";然后用 used 处理"顺序敏感"的排列,用 start 处理"顺序无关"的子集组合,用剪枝处理重复和不可能分支。模板只有十行,难的是把问题翻译成模板。

💡 回溯题的时间复杂度几乎都是指数级,面试时主动说出"最坏 O(n!)"或"O(2^n)"并说明为什么,比闷头写代码得分高得多。

练习题: