LeetCode-Go 回溯算法专题：排列组合、N 皇后、数独与 DFS/BFS 模板全解析

LeetCode-Go 回溯算法专题：排列组合、N 皇后、数独与 DFS/BFS 模板全解析

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本文以 LeetCode-Go 仓库中标记为 ✅（全部完成）的 Backtracking 专题文档 为核心骨架，系统梳理回溯算法（Backtracking）在力扣题解中的完整应用地图：排列、组合、子集、N 皇后、数独、四方向搜索、Trie 剪枝与 BFS 优化等经典题型。文章不仅完整保留原专题文档中的 DFS 与 BFS 两套可复用模板，还结合仓库leetcode/目录下的真实源码（如 46. Permutations.go、51. N-Queens.go、37. Sudoku Solver.go）逐行剖析回溯的「选择—递归—撤销」三件套，读完后你将掌握用 Go 语言写出可去重、可剪枝、可位运算优化的通用回溯解法。

一、Backtracking 专题覆盖范围总览

原专题文档在仓库 ctl/template/Backtracking.md 中开宗明义，将回溯类题目划分为以下 9 大子类，每个子类都给出了对应题号，方便按图索骥、集中刷题：

问题类型	对应题号	核心考点
排列问题 Permutations	46、47、60、526、996	全排列 / 排列去重 / 康托展开 / 位掩码计数
组合问题 Combination	39、40、77、216	组合枚举 / 去重 / 剪枝
排列与组合杂交	1079	状态压缩 + 组合计数
N 皇后终极解法（二进制解法）	51、52	行列斜线冲突检测 / 位运算加速
数独问题	37	行、列、九宫格合法性校验
四个方向搜索	79、212、980	网格 DFS / 前缀树剪枝
子集合问题	78、90	子集枚举 / 子集去重
Trie	208、211	前缀树结构 + 通配符回溯
BFS 优化	126、127	双向 BFS / 分层扩展

在仓库根 README.md 的算法总表中，回溯还被列为独立的经典算法大类，并列举了装载问题、批处理作业调度、三角形符号问题、n 皇后问题、0-1 背包、最大团问题、图 m 着色问题、旅行商问题（TSP）、圆排列问题、电路板排列问题、连续邮资问题等经典回溯应用场景。专题文档与其互为印证：只要掌握「状态空间树 + 递归 + 剪枝」这一回溯内核，就能覆盖从组合枚举到图论 NP 问题的统一解法范式。

二、排列问题：used 数组标记与全排列生成

排列问题关注顺序，因此需要记录「当前元素是否已被使用」。仓库中 46. Permutations.go 的实现是教科书式的排列回溯：

func permute(nums []int) [][]int { if len(nums) == 0 { return [][]int{} } used, p, res := make([]bool, len(nums)), []int{}, [][]int{} generatePermutation(nums, 0, p, &res, &used) return res } func generatePermutation(nums []int, index int, p []int, res *[][]int, used *[]bool) { if index == len(nums) { temp := make([]int, len(p)) copy(temp, p) *res = append(*res, temp) return } for i := 0; i < len(nums); i++ { if !(*used)[i] { (*used)[i] = true p = append(p, nums[i]) generatePermutation(nums, index+1, p, res, used) p = p[:len(p)-1] (*used)[i] = false } } return }

可以提炼出回溯的三段式骨架：

1. 终止条件：index == len(nums)时把当前排列p的副本存入结果（注意copy，避免共享底层数组被后续回溯污染）；
2. 横向遍历：每一层都从头扫描nums，用used数组跳过已选元素；
3. 递归与撤销：先标记used[i] = true并append，递归下一层，返回后再p = p[:len(p)-1]撤销选择、used[i] = false复位标记。

第 47 题（Permutations II）在此基础上对nums预先排序，并在横向循环中跳过「与前一个相等且前一个未被使用」的元素，即可完成去重。第 60 题（Permutation Sequence）则利用阶乘计数直接定位第 k 个排列，避免生成全部排列，属于回溯 + 数学的经典结合；第 526 题（Beautiful Arrangement）与第 996 题（Number of Squareful Arrays）进一步把「可排列性」的判断内联进剪枝条件，属于排列回溯的状态压缩变体。

三、组合问题与去重：DFS 模板详解

组合问题不关心顺序，因此递归时从index向后推进即可天然避免重复。专题文档给出了一个高度通用的 DFS 模板（以组合总和 II 为例），这也是全仓库被反复引用的核心模板：

func combinationSum2(candidates []int, target int) [][]int { if len(candidates) == 0 { return [][]int{} } c, res := []int{}, [][]int{} sort.Ints(candidates) findcombinationSum2(candidates, target, 0, c, &res) return res } func findcombinationSum2(nums []int, target, index int, c []int, res *[][]int) { if target == 0 { b := make([]int, len(c)) copy(b, c) *res = append(*res, b) return } for i := index; i < len(nums); i++ { if i > index && nums[i] == nums[i-1] { // 这里是去重的关键逻辑 continue } if target >= nums[i] { c = append(c, nums[i]) findcombinationSum2(nums, target-nums[i], i+1, c, res) c = c[:len(c)-1] } } }

这段模板包含三个值得反复品味的要点：

1. 排序是去重的前提：入口先sort.Ints(candidates)，让相同元素相邻，去重才能通过相邻比较完成；
2. i > index && nums[i] == nums[i-1]是去重关键：只跳过「同一层递归中重复出现的元素」，而不会误伤不同层（如[1,1,6]中第二个1在不同分支是合法的）。这是组合去重与排列去重的最大区别——去重发生在横向循环层，而非纵向递归层；
3. target >= nums[i]是天然的剪枝：数组已排序，一旦当前元素大于剩余目标值，后续元素只会更大，可以整体continue，同时通过i+1保证每个元素只使用一次。

这套模板向下可覆盖第 39 题（Combination Sum，允许重复使用元素，递归参数改为i即可）、第 77 题（Combinations）、第 216 题（Combination Sum III）；向上与第 1079 题（Letter Tile Possibilities）的排列组合杂交模型衔接——杂交模型通常先在状态空间中枚举组合，再对每个组合计算其排列数，本质仍是「选择 + 计数」。

四、子集合问题：78 与 90

子集问题可以看作组合问题的「全集输出」：组合问题输出满足约束的解，子集问题输出所有前缀/路径。第 78 题（Subsets）在每层递归进入时就把当前路径快照存入结果，从而收集所有长度的子集；第 90 题（Subsets II）引入与组合模板完全一致的相邻去重逻辑（i > index && nums[i] == nums[i-1]），在排序后即可输出不重复子集。

从源码结构看，78. Subsets、90. Subsets-II 与 40. Combination Sum II 共用同一套「排序 + 下标推进 + 去重」骨架，区别仅在结果收集时机与剪枝条件，这印证了回溯题型的同构性：记忆一套模板，改三处细节（收集时机、去重方向、剪枝条件），即可横向迁移。

五、N 皇后：从 DFS 冲突数组到二进制位运算

专题文档特别标注 N 皇后为「终极解法（二进制解法）」。仓库 51. N-Queens.go 给出了两套解法，恰好形成从入门到进阶的完整链路。

5.1 解法一：DFS + 列 / 主对角 / 副对角数组

func putQueen(n, index int, col, dia1, dia2 *[]bool, row *[]int, res *[][]string) { if index == n { *res = append(*res, generateBoard(n, row)) return } for i := 0; i < n; i++ { // 尝试将第 index 行的皇后摆放在第 i 列 if !(*col)[i] && !(*dia1)[index+i] && !(*dia2)[index-i+n-1] { *row = append(*row, i) (*col)[i] = true (*dia1)[index+i] = true (*dia2)[index-i+n-1] = true putQueen(n, index+1, col, dia1, dia2, row, res) (*col)[i] = false (*dia1)[index+i] = false (*dia2)[index-i+n-1] = false *row = (*row)[:len(*row)-1] } } return }

核心在于用三个一维布尔数组把 O(n²) 的棋盘冲突检查降为 O(1) 查询：

• col[i]：第i列是否已有皇后；
• dia1[index+i]：主对角线（\）编号，同一主对角线上行 + 列为常数；
• dia2[index-i+n-1]：副对角线（/）编号，同一副对角线上行 - 列为常数，加n-1偏移避免负数下标。

generateBoard负责把row（每行皇后的列号）渲染成棋盘字符串。这套「行号做递归深度、列号做横向枚举」的模型，正是后续二进制解法的雏形。

5.2 解法二：二进制位运算（终极解法）

func solveNQueens2(n int) (res [][]string) { // ... 预生成 placements 字符串 ... var construct func(prev []int) construct = func(prev []int) { if len(prev) == n { // 生成棋盘方案并存入 res return } occupied := 0 for i := range prev { dist := len(prev) - i bit := 1 << prev[i] occupied |= bit | bit<<dist | bit>>dist // 列 + 两条斜线一次性合并 } prev = append(prev, -1) for i := 0; i < n; i++ { if (occupied>>i)&1 != 0 { continue } prev[len(prev)-1] = i construct(prev) } } construct(make([]int, 0, n)) return }

二进制解法的精妙在于：occupied |= bit | bit<<dist | bit>>dist用一次位运算把当前已放置皇后的「列攻击线」与「左右斜线攻击线」全部合并到一个整数中，任何被占用的列只需(occupied>>i)&1 != 0一次位测试即可判定。相比布尔数组，它省掉了dia1/dia2两个数组的空间，且位运算天然支持并行冲突检测，是 N 皇后性能优化的终极形态，第 52 题（N-Queens II）只统计方案数时可直接复用该框架。

六、数独问题：37 题的递归填格模型

数独是回溯在「二维约束满足」上的典型应用。仓库 37. Sudoku Solver.go 采用「预收集空格 + 逐格试填」的策略：

type position struct { x int y int } func solveSudoku(board [][]byte) { pos, find := []position{}, false for i := 0; i < len(board); i++ { for j := 0; j < len(board[0]); j++ { if board[i][j] == '.' { pos = append(pos, position{x: i, y: j}) } } } putSudoku(&board, pos, 0, &find) } func putSudoku(board *[][]byte, pos []position, index int, succ *bool) { if *succ == true { return } if index == len(pos) { *succ = true return } for i := 1; i < 10; i++ { if checkSudoku(board, pos[index], i) && !*succ { (*board)[pos[index].x][pos[index].y] = byte(i) + '0' putSudoku(board, pos, index+1, succ) if *succ == true { return } (*board)[pos[index].x][pos[index].y] = '.' } } }

实现细节值得注意：

1. 先遍历棋盘把所有.空格收集进pos数组，递归深度即为空格总数；
2. 递归前用checkSudoku做三重复核：横行无重复、竖行无重复、所在 3×3 九宫格无重复（posx, posy := pos.x-pos.x%3, pos.y-pos.y%3定位宫格左上角）；
3. 由于数独只有一个解，用succ *bool标志位实现「找到解立即回溯退出」，避免无谓的继续搜索——这是「是否存在解 / 唯一解」类回溯题的通用收尾技巧。

七、四方向搜索：79、212 与 980 的网格回溯

网格类回溯统一使用「上下左右」方向数组驱动递归。仓库 79. Word Search.go 定义全局方向表并配合visited矩阵：

var dir = [][]int{ {-1, 0}, {0, 1}, {1, 0}, {0, -1}, } func searchWord(board [][]byte, visited [][]bool, word string, index, x, y int) bool { if index == len(word)-1 { return board[x][y] == word[index] } if board[x][y] == word[index] { visited[x][y] = true for i := 0; i < 4; i++ { nx := x + dir[i][0] ny := y + dir[i][1] if isInBoard(board, nx, ny) && !visited[nx][ny] && searchWord(board, visited, word, index+1, nx, ny) { return true } } visited[x][y] = false } return false }

要点：visited[x][y]在进入递归前标记、回溯后复位，保证同一条搜索路径不重复经过同一格；入口exist从每个格子出发尝试，一旦任一方向命中立即短路返回。第 212 题（Word Search II）把多单词匹配交给 Trie 前缀树剪枝——前缀不匹配就整体剪掉整棵子树，避免对每个单词独立 DFS；第 980 题（Unique Paths III）则在 980. Unique Paths III.go 中用empty计数「剩余必须经过的空格数」，走到终点时要求empty == 0才累加方案数，把「恰好遍历所有空格」的约束精确翻译为计数条件，其中注释明确提醒：可走步数要加一，因为终点格子也算一步。

八、Trie：前缀树与通配符回溯

专题把 Trie 单独列为一类，因为前缀树是回溯的重要加速器（尤其在 212 题这类多模式匹配中）。仓库 208. Implement Trie (Prefix Tree).go.go) 给出了最简实现：

type Trie struct { isWord bool children map[rune]*Trie }

• Insert：沿字符逐层创建/复用子节点，末尾标记isWord = true；
• Search：沿路径查找并校验isWord；
• StartsWith：仅校验路径存在，不要求单词完整。

第 211 题（Design Add and Search Words Data Structure）在该结构上叠加通配符回溯：当字符为.时，遍历当前节点的所有子节点逐一递归尝试，命中即返回——这是「回溯 + 数据结构」组合的经典案例，也解释了为何专题把 Trie 与回溯并列编排。

九、BFS 优化：126、127 与分层扩展模板

专题文档将 BFS 优化（第 126、127 题）一并纳入回溯专题，因为两者共享「状态空间搜索」的思维框架，且 BFS 常与回溯互为替代/补充。文档给出了一个独立于具体题目的通用 BFS 模板（层次遍历 + 多源起点）：

func updateMatrix_BFS(matrix [][]int) [][]int { res := make([][]int, len(matrix)) if len(matrix) == 0 || len(matrix[0]) == 0 { return res } queue := make([][]int, 0) for i, _ := range matrix { res[i] = make([]int, len(matrix[0])) for j, _ := range res[i] { if matrix[i][j] == 0 { res[i][j] = -1 // 用 -1 标记多源 BFS 的初始层 queue = append(queue, []int{i, j}) } } } level := 1 for len(queue) > 0 { size := len(queue) for size > 0 { size -= 1 node := queue[0] queue = queue[1:] i, j := node[0], node[1] for _, direction := range [][]int{{-1, 0}, {1, 0}, {0, 1}, {0, -1}} { x := i + direction[0] y := j + direction[1] if x < 0 || x >= len(matrix) || y < 0 || y >= len(matrix[0]) || res[x][y] < 0 || res[x][y] > 0 { continue } res[x][y] = level queue = append(queue, []int{x, y}) } } level++ } for i, row := range res { for j, cell := range row { if cell == -1 { res[i][j] = 0 } } } return res }

模板要点拆解：

1. 多源起点：所有值为 0 的格子同时入队作为第 0 层（用-1临时标记，最后统一还原为 0），避免对每个起点单独 BFS；
2. 按层扩展：size := len(queue)固定当前层大小，内层循环只消费当前层，level每层自增，天然得到「到最近 0 的距离」；
3. 访问控制：res[x][y] < 0 || res[x][y] > 0的双重判断同时挡住起点（负数）与已赋值格（正数），保证每个格子只被赋值一次（首次即最短距离）。

第 127 题（Word Ladder）与第 126 题（Word Ladder II）正是把该模板应用于单词状态图：每次替换一个字符生成邻居状态，用 BFS 求最短转换长度；126 题需要输出全部最短路径时，则通常配合「记录前驱」再做回溯还原，这也是 BFS 与回溯在同一道题内协同的典型结构。

十、在仓库中如何定位与验证这些题解

• 专题索引：回溯专题的完整分类与题号清单见 ctl/template/Backtracking.md，根目录 README.md 的 Algorithm 表格中同样给出回溯算法大类的经典问题清单，二者配套阅读可快速建立知识地图；
• 单题源码：每个题目独立成目录，命名规范为「题号.题目名」，例如 0040.Combination-Sum-II、0051.N-Queens、0037.Sudoku-Solver、0079.Word-Search 等，目录内含.go实现文件与_test.go测试文件；
• 本地运行验证：仓库根目录的 go.mod 定义了模块依赖，配合 gotest.sh 脚本可批量执行测试；在任意题解目录下用go test ./...（或go test -v）即可运行该题的单测，用go run亦可直接验证算法行为；
• 模板组织：所有专题模板统一存放在 ctl/template 目录，若想批量生成或维护各专题的索引文档，可参考 ctl 下的 Go 命令行工具实现。

结语：回溯的通用心法

综合本专题与仓库源码，可以归纳出回溯解题的通用心法：递归深度对应「状态维度」，横向循环对应「候选集合」，撤销操作保证状态空间树的无损遍历，剪枝（排序去重、约束预判、位运算加速、前缀树截断）决定算法能否从「能跑」走向「跑赢」。专题文档中 9 大分类、40 余道题目的源码在 LeetCode-Go 仓库中均有 100% 测试覆盖的实现可循，建议按「排列 → 组合 → 子集 → 棋盘/网格 → 数据结构辅助」的顺序逐一攻克，每道题都对照模板比较「收集时机、去重方向、剪枝条件」三处差异，即可把回溯内化为条件反射。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go