LeetCode 60. Permutation Sequence 全排列序列LeetCode-Go 仓库 DFS 解法源码级解析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文以 LeetCode-Go 仓库中 60. Permutation Sequence 题解文档为主线完整还原题目定义、约束条件与示例并深入解析仓库中 DFS 暴力枚举实现 60. Permutation Sequence.go 的每一行逻辑与复杂度成因。读完后你将掌握「按字典序求第 k 个全排列」的 DFS 回溯写法、其 O(n!) 时间代价的由来以及题解文档中点名提示的「更优解法」——基于阶乘数系统的逐位构造法。一、题目理解什么是第 k 个排列集合[1, 2, 3, ..., n]中所有元素共能组成n! 种不重复的排列。将这些排列按字典序大小顺序列出并逐一编号第 k 个就是题目要求的输出。以 n 3 为例全部 6 种排列按序排列为123132213231312321给定 n 和 k返回第 k 个排列序列。约束条件n 的取值范围为1 到 9含端点k 的取值范围为1 到 n!含端点。这一约束意味着 n 最大为 9n! 最大为 362880暴力枚举在最坏情况下要遍历 36 万量级的叶子节点仍是可运行但明显低效的规模——这正是题解文档提示「想想更优的解法」的原因。官方示例示例 1Input: n 3, k 3 Output: 213示例 2Input: n 4, k 9 Output: 2314可以从 n 3 的排列表中直接验证示例 1第 3 个排列正是213。示例 2 需要 n 4 的字典序全排列表共 24 种第 9 个为2314。二、题目大意给出集合[1, 2, 3, …, n]其所有元素共有 n! 种排列。按大小顺序列出所有排列情况并一一标记当 n 3 时所有排列依次为123、132、213、231、312、321。给定 n 和 k返回第 k 个排列。本质上这是一道「全排列生成 字典序截断」的题目要么老老实实生成全部排列并数到第 k 个DFS 暴力法要么利用排列数与阶乘之间的数学关系直接定位每一位阶乘数系统法。三、解题思路DFS 暴力枚举仓库给出的解法题解文档在「解题思路」一节给出的核心策略是用 DFS 暴力枚举这种做法时间复杂度特别高想想更优的解法。也就是说仓库选择先用正确但低效的方案打开思路从空排列出发用深度优先搜索逐位填充数字used数组标记已用数字每生成一个完整排列深度达到 n就令计数器 k 减一当 k 减到 0 时当前排列即为第 k 个排列立即停止。这种写法把「第 k 个」转化为「深度优先遍历顺序中的第 k 个叶子节点」依靠 DFS 天然按字典序访问叶子节点的性质无需额外排序。四、源码解析逐行拆解 DFS 实现仓库中的实际实现位于 60. Permutation Sequence.go完整代码如下与题解文档 0060.Permutation-Sequence.md 中的代码一致package leetcode import ( fmt strconv ) func getPermutation(n int, k int) string { if k 0 { return } used, p, res : make([]bool, n), []int{}, findPermutation(n, 0, k, p, res, used) return res } func findPermutation(n, index int, k *int, p []int, res *string, used *[]bool) { fmt.Printf(n %v index %v k %v p %v res %v user %v\n, n, index, *k, p, *res, *used) if index n { *k-- if *k 0 { for _, v : range p { *res strconv.Itoa(v 1) } } return } for i : 0; i n; i { if !(*used)[i] { (*used)[i] true p append(p, i) findPermutation(n, index1, k, p, res, used) p p[:len(p)-1] (*used)[i] false } } return }4.1 入口函数getPermutationfunc getPermutation(n int, k int) string { if k 0 { return } used, p, res : make([]bool, n), []int{}, findPermutation(n, 0, k, p, res, used) return res }used长度为 n 的布尔数组used[i] true表示数字i1已被选用p当前路径记录已选数字的下标后续统一加 1 还原为真实数字res最终结果字符串通过指针传入便于在递归深处直接写入k同样以指针传入因为 k 在递归中需要被跨层级修改每找到一个完整排列就递减if k 0 { return }对非法输入k 0的防御性处理与测试用例{3, 0}期望输出相对应。4.2 递归主体findPermutation递归函数的五个参数含义为参数类型含义nint排列长度数字个数indexint当前已填充的位数等于递归深度k*int指向剩余计数的指针叶子节点处递减p[]int当前已选数字下标序列路径res*string指向结果字符串的指针used*[]bool指向使用标记数组的指针递归终止条件if index n { *k-- if *k 0 { for _, v : range p { *res strconv.Itoa(v 1) } } return }当深度达到 n 时p已构成一个完整排列如下标[0, 1, 2]对应123。此时*k--排列计数减一表示「跳过了一个排列」若*k 0说明当前正是第 k 个排列将下标序列p逐个1并用strconv.Itoa转成字符拼接到res无论是否命中都会return回溯继续遍历剩余分支——但由于命中后res已非空后续叶子节点虽然仍会被访问此实现没有显式剪枝结果不会再被覆盖。未达深度的分支选择逻辑for i : 0; i n; i { if !(*used)[i] { (*used)[i] true p append(p, i) findPermutation(n, index1, k, p, res, used) p p[:len(p)-1] (*used)[i] false } }每层从下标 0 开始尝试所有未使用数字保证生成顺序严格符合字典序p append(p, i)选入当前数字递归进入下一层p p[:len(p)-1]与(*used)[i] false是标准的回溯撤销操作恢复现场以尝试下一个分支。4.3 关于代码中的调试打印实现的第一行保留了fmt.Printf(n %v index %v k %v p %v res %v user %v\n, ...)调试输出注意其中user为笔误实际意图是输出used数组。运行时它会打印每次递归进入时的参数快照方便观察 DFS 的访问轨迹正式提交 LeetCode 时需删除该行因为它会让输出与判定产生额外 IO 开销。4.4 复杂度分析时间复杂度O(n!)。最坏情况下 k n!需要完整遍历所有排列的叶子节点才能命中最后一个即便提前命中遍历规模也与 k 同阶整体受 n! 上界约束。空间复杂度O(n)。递归栈深度最大为 nused与p均为 O(n)res长度为 n无额外与排列数同阶的存储。正是由于 O(n!) 的时间代价题解文档才明确指出「这种做法时间复杂度特别高」引导读者思考基于阶乘数系统的数学解法。五、测试用例验证仓库测试文件如何断言仓库为本题提供了单元测试 60. Permutation Sequence_test.go采用结构体切片驱动的表驱动测试模式type question60 struct { para60 ans60 } type para60 struct { n int k int } type ans60 struct { one string }测试用例共 3 组输入(n, k)期望输出(3, 3)213(4, 9)2314(3, 0)断言逻辑如下for _, q : range qs { a, p : q.ans60, q.para60 got : getPermutation(p.n, p.k) if got ! a.one { t.Fatalf(input %v expected %v got %v, p, a.one, got) } fmt.Printf(【input】:%v 【output】:%v\n, p, got) }前两组用例直接对应题目官方示例第三组(3, 0)覆盖了入口函数if k 0的防御分支验证非法输入返回空串。这说明该实现不仅针对正常输入还考虑了参数边界的健壮性。在仓库根目录执行go test ./leetcode/0060.Permutation-Sequence/...即可运行该用例或参考 gotest.sh 了解仓库整体的测试脚本约定。六、更优解法探讨阶乘数系统逐位定位题解文档点名的方向题解文档明确留下「想想更优的解法」的提示。这里的经典优化思路是阶乘数系统factorial number system也称为康托展开的逆运算不生成任何排列而是直接通过数学计算确定第 k 个排列的每一位。6.1 核心原理给定 n 个数字以第 1 位数字 d 为例若固定 d 为某个值剩余 n-1 个数字可组成(n-1)!种排列因此字典序下每 (n-1)! 个排列共享同一个首位首位确定后k 对 (n-1)! 取余并继续在剩余 n-1 个数字中定位第 2 位依次类推。逐位推导过程为k k - 1 // 转为 0 基索引便于整除 第 1 位下标 k / (n-1)! k k % (n-1)! 第 2 位下标 k / (n-2)! k k % (n-2)! ...其中每一步的「下标」都指向**当前剩余数字集合按升序**中的第几个数字选完后将其从集合中移除再进入下一位。6.2 以 n 3, k 3 为例手算k 3 - 1 2剩余数字[1, 2, 3]第 1 位2 / 2! 1取剩余数字第 1 个0 基即2k 2 % 2 0剩余[1, 3]第 2 位0 / 1! 0取1k 0 % 1 0剩余[3]第 3 位取3。结果213与示例 1 及仓库测试用例完全一致。6.3 以 n 4, k 9 为例手算k 9 - 1 8剩余[1, 2, 3, 4]第 1 位8 / 3! 1取2k 8 % 6 2剩余[1, 3, 4]第 2 位2 / 2! 1取3k 2 % 2 0剩余[1, 4]第 3 位0 / 1! 0取1剩余[4]第 4 位取4。结果2314与示例 2 及仓库测试用例一致。6.4 两种方法对比维度DFS 暴力枚举仓库实现阶乘数系统逐位构造时间复杂度O(n!)O(n²)每次从剩余集合取第 i 个元素空间复杂度O(n)O(n)代码复杂度低回溯模板直接套用中需维护阶乘表与剩余数字集合适用场景理解全排列生成与回溯大规模 n 下直接命中第 k 个排列n ≤ 9 时两者都能在毫秒级内完成但 n 一旦增大例如 n 1212! ≈ 4.79 亿DFS 将完全不可行而阶乘数系统依旧可以在 O(n²) 内求解。这也是 LeetCode 官方将该题定位为数学题的原因。七、小结与延伸阅读本文围绕 LeetCode-Go 仓库的 0060.Permutation-Sequence.md 题解文档完成了三件事完整复述题目字典序下第 k 个全排列的定义、n ∈ [1, 9] 与 k ∈ [1, n!] 的约束、两个官方示例源码级解析仓库解法逐行拆解 60. Permutation Sequence.go 的入口函数、递归回溯、终止条件与复杂度并借助 60. Permutation Sequence_test.go 中的三组用例验证正确性顺着题解文档的提示探索更优解用阶乘数系统康托展开逆运算将时间复杂度从 O(n!) 降到 O(n²)并用手算验证两个示例。对于想继续深入同类问题的读者仓库中 46. Permutations全排列回溯与 47. Permutations II含重复元素的全排列使用了相同的 DFS used回溯骨架可作为对比阅读而本题的数学解法思路也与「按字典序排名」类问题如康托展开一脉相承。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考