归档157

547 字

3 分钟

DFS 回溯模板整理

2026-07-01

数据结构与算法

DFS

回溯

DFS 回溯模板整理#

学习搜索算法时，DFS 和回溯经常放在一起出现。刚开始容易混乱：递归什么时候结束，路径什么时候加入答案，为什么递归回来还要撤销选择。

今天用全排列问题整理一个基础模板。

1、问题描述#

给定一个数组：

1
[1, 2, 3]

要求输出所有排列：

1
[1, 2, 3]
2
[1, 3, 2]
3
[2, 1, 3]
4
[2, 3, 1]
5
[3, 1, 2]
6
[3, 2, 1]

这个问题适合用 DFS 回溯，因为每一层都在选择一个还没使用过的数字。

2、先写出三个核心变量#

回溯里我习惯先想三个东西：

1
path：当前已经选择的路径
2
used：某个数字是否已经用过
3
ans：保存最终答案

然后每次递归都做一件事：从还没用过的数字里选一个，放进 path。

3、Python 模板#

1
def permute(nums):
2
    ans = []
3
    path = []
4
    used = [False] * len(nums)
5

6
    def dfs():
7
        if len(path) == len(nums):
8
            ans.append(path.copy())
9
            return
10

11
        for i in range(len(nums)):
12
            if used[i]:
13
                continue
14

15
            path.append(nums[i])
16
            used[i] = True
17

18
            dfs()
19

20
            used[i] = False
21
            path.pop()
22

23
    dfs()
24
    return ans
25

26
print(permute([1, 2, 3]))

这里最重要的是递归后的两行：

1
used[i] = False
2
path.pop()

它们表示撤销当前选择，回到进入这一层之前的状态，然后继续尝试下一个数字。

4、为什么要 path.copy()#

保存答案时不能直接写：

1
ans.append(path)

因为 path 是一个会继续变化的列表。后面不断 append 和 pop，答案里的引用也会跟着变。应该保存当前路径的副本：

1
ans.append(path.copy())

这是回溯题里很常见的小坑。

5、套模板时先问三个问题#

以后遇到类似题目，可以先问：

1
1. 递归终止条件是什么？
2
2. 每一层有哪些选择？
3
3. 做出选择后，递归回来要撤销什么？

比如组合问题、子集问题、棋盘搜索问题，都可以从这三个问题开始拆。

总结#

DFS 回溯的写法可以概括成：选择、递归、撤销选择。全排列是最基础的例子，能看清楚 path、used 和 ans 的作用。模板背下来不是目的，关键是理解每一层递归都在枚举当前可选项。

文章分享

如果这篇文章对你有帮助，欢迎分享给更多人！

DFS 回溯模板整理

https://blog.tjcheng.cn/posts/daily/2026-07-01/dfs-backtracking-template/

作者

TengJinCheng

发布于

2026-07-01

许可协议

CC BY-NC-SA 4.0

博客文章 Frontmatter 模板整理

五险一金到底包含什么

音乐

音乐