示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本文基于 doocs/leetcode 开源题解仓库中 0046.Permutations 题解文档英文版见 README_EN.md展开围绕「全排列」这一经典回溯问题系统讲解 DFS 回溯算法的设计思路、状态撤销机制与复杂度分析并对照仓库中 Python、Java、C、Go、TypeScript、Rust、JavaScript、C# 八种语言的 Solution 源码 逐份解读实现差异。读完本文你将掌握按位置填数 标记已用元素这一回溯范式并能将其迁移到组合、子集、N 皇后等同类问题上。一、题目理解求互异数组的全部排列题目要求给定一个不含重复数字的数组nums返回其所有可能的全排列答案可按任意顺序返回。示例 1nums [1,2,3]输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]共3! 6个排列示例 2nums [0,1]输出[[0,1],[1,0]]共2! 2个排列示例 3nums [1]输出[[1]]共1! 1个排列。约束条件与 LeetCode 原题一致文档中明确列出约束项范围数组长度1 nums.length 6元素取值-10 nums[i] 10元素互异性nums中所有整数互不相同三个约束共同决定了本题的解题空间n 6意味着全排列总数最多为6! 720规模完全允许暴力枚举元素互异则免去了去重处理是后续 47 题全排列 II才需要面对的问题。二、思路分析为什么选择 DFS 回溯在动手写代码前文档中的思考部分给出了非常清晰的推导过程这里完整复述并展开语言内置函数或多层循环可行但不可推广。n 6时n!规模可以接受但n是不固定的输入参数我们无法预先写死循环层数——写 3 层循环只能解n 3换一个n 5的用例就失效了。排列的本质是每个位置选一个尚未使用的数。如果某个数在同一排列中被重复使用结果就不再是排列因此必须对已使用状态做标记。生成过程天然符合深度优先搜索。我们把问题拆成按位置填数先填第 1 位再填第 2 位……每填完一位就向下一层递归直到所有位置填满。这正是 DFS 的递归树形态。因此最终方案确定为DFS深度优先搜索 回溯配合一个布尔数组标记已选下标。文档给出的时间复杂度结论是 $O(n \times n!)$其中 $n$ 是数组长度——一共有 $n!$ 个排列每个排列需要 $O(n)$ 的时间来构造与输出规模严格相符。三、算法流程详解dfs(i)的完整语义设n len(nums)设计递归函数dfs(i)表示前i个位置已经填好现在需要填第i 1个位置。函数内部执行以下步骤递归出口若i n说明所有位置都已填满将当前排列快照加入答案数组返回枚举候选遍历数组所有下标j跳过已被标记使用的位置vis[j] true尝试填入把nums[j]放入排列的第i位t[i] nums[j]并标记vis[j] true递归下一层调用dfs(i 1)继续填下一位撤销状态回溯递归返回后将vis[j]复原为false。若使用动态数组如 Java 的List还需把刚加入的元素从排列尾部移除。其中第 5 步撤销是整个回溯算法的灵魂只有先撤销本次选择才能让同一层循环中的下一个候选数拥有相同的初始状态从而穷举出互不重复的完整排列空间。我们以nums [1,2,3]手动推演前几层递归树dfs(0)第 0 位选 1 → vis[T,F,F] └─ dfs(1)第 1 位选 2 → vis[T,T,F] └─ dfs(2)第 2 位选 3 → 得到 [1,2,3] └─ 撤销 3 └─ 撤销 2第 1 位改选 3 → vis[T,F,T] └─ dfs(2)第 2 位选 2 → 得到 [1,3,2] ...每一层都遍历未使用的所有候选当递归触底时即收获一个完整排列最终共收获n!个结果。四、多语言实现对照8 份源码逐语言解读仓库为该题维护了 8 种语言的实现文件与 README 题解文档 中的代码块一一对应。所有实现共享同一套算法骨架vis[]标记 按位填充 递归 撤销。下面逐份解读。4.1 Python3 —— Solution.pyclass Solution: def permute(self, nums: List[int]) - List[List[int]]: def dfs(i: int): if i n: ans.append(t[:]) return for j, x in enumerate(nums): if not vis[j]: vis[j] True t[i] x dfs(i 1) vis[j] False n len(nums) vis [False] * n t [0] * n ans [] dfs(0) return ans实现要点vis [False] * n是已使用下标标记数组t [0] * n是定长的结果槽位ans收集全部排列记录结果时使用t[:]切片拷贝而非直接append(t)避免后续回溯修改t导致已存结果被污染——这是回溯类题目最经典的坑之一enumerate(nums)同时取出下标j与值xvis[j]标记的是下标而非值因为题目保证元素互异下标与值一一对应。4.2 Java —— Solution.javaclass Solution { private ListListInteger ans new ArrayList(); private ListInteger t new ArrayList(); private boolean[] vis; private int[] nums; public ListListInteger permute(int[] nums) { this.nums nums; vis new boolean[nums.length]; dfs(0); return ans; } private void dfs(int i) { if (i nums.length) { ans.add(new ArrayList(t)); return; } for (int j 0; j nums.length; j) { if (!vis[j]) { vis[j] true; t.add(nums[j]); dfs(i 1); t.remove(t.size() - 1); vis[j] false; } } } }实现要点使用ListInteger t动态维护当前排列递归前add回溯后remove(t.size() - 1)配合vis的置位/复原完成状态回退收集结果时用new ArrayList(t)做深拷贝原因与 Python 的t[:]相同四个成员变量ans、t、vis、nums通过类字段共享避免在递归中反复传参这是 Java 风格的常见写法。4.3 C —— Solution.cppclass Solution { public: vectorvectorint permute(vectorint nums) { int n nums.size(); vectorvectorint ans; vectorint t(n); vectorbool vis(n); auto dfs - void { if (i n) { ans.emplace_back(t); return; } for (int j 0; j n; j) { if (!vis[j]) { vis[j] true; t[i] nums[j]; dfs(i 1); vis[j] false; } } }; dfs(0); return ans; } };实现要点使用 C23 的deducing this语法定义可自递归的 Lambda把辅助函数收敛在permute内部无需额外声明全局/成员函数t采用定长vectorint t(n)按索引赋值t[i] nums[j]因此回溯时只需还原vis[j]无需弹出元素收集结果直接ans.emplace_back(t)利用t的拷贝构造生成独立副本。4.4 Go —— Solution.gofunc permute(nums []int) (ans [][]int) { n : len(nums) t : make([]int, n) vis : make([]bool, n) var dfs func(int) dfs func(i int) { if i n { ans append(ans, slices.Clone(t)) return } for j, x : range nums { if !vis[j] { vis[j] true t[i] x dfs(i 1) vis[j] false } } } dfs(0) return }实现要点利用命名返回值(ans [][]int)省去显式 return 语句关键细节是slices.Clone(t)Go 的切片是引用类型append(ans, t)只会让所有结果共享同一个底层数组回溯后数据会被覆盖克隆才能生成独立副本依赖 Go 1.21 的slices标准库包与 C 相同t是定长切片撤销只需复位vis[j]。4.5 TypeScript —— Solution.tsfunction permute(nums: number[]): number[][] { const n nums.length; const ans: number[][] []; const vis: boolean[] Array(n).fill(false); const t: number[] Array(n).fill(0); const dfs (i: number) { if (i n) { ans.push(t.slice()); return; } for (let j 0; j n; j) { if (!vis[j]) { vis[j] true; t[i] nums[j]; dfs(i 1); vis[j] false; } } }; dfs(0); return ans; }实现要点结构与 JavaScript 版本完全一致仅增加类型标注number[]、number[][]、boolean[]结果快照使用t.slice()——数组的浅拷贝效果等同 Python 的t[:]与 Go 的slices.Clone(t)。4.6 Rust —— Solution.rsimpl Solution { pub fn permute(nums: Veci32) - VecVeci32 { let n nums.len(); let mut ans Vec::new(); let mut t vec![0; n]; let mut vis vec![false; n]; fn dfs( nums: Veci32, n: usize, t: mut Veci32, vis: mut Vecbool, ans: mut VecVeci32, i: usize ) { if i n { ans.push(t.clone()); return; } for j in 0..n { if !vis[j] { vis[j] true; t[i] nums[j]; dfs(nums, n, t, vis, ans, i 1); vis[j] false; } } } dfs(nums, n, mut t, mut vis, mut ans, 0); ans } }实现要点由于 Rust 闭包捕获可变引用的借用约束较繁琐这里选择了独立嵌套函数fn dfs把nums、n、t、vis、ans全部作为显式参数传递t使用vec![0; n]定长分配、按索引赋值收集结果时t.clone()复制一份vis与t均以mut传入递归层间共享同一份状态与其余语言语义一致。4.7 JavaScript —— Solution.js/** * param {number[]} nums * return {number[][]} */ var permute function (nums) { const n nums.length; const ans []; const vis Array(n).fill(false); const t Array(n).fill(0); const dfs i { if (i n) { ans.push(t.slice()); return; } for (let j 0; j n; j) { if (!vis[j]) { vis[j] true; t[i] nums[j]; dfs(i 1); vis[j] false; } } }; dfs(0); return ans; };实现要点闭包dfs直接捕获外层n、ans、vis、t无需参数传递是 JS 惯用写法t.slice()快照 vis置位/复位与 TypeScript 版本逻辑完全相同。4.8 C# —— Solution.cspublic class Solution { public IListIListint Permute(int[] nums) { var ans new ListIListint(); var t new Listint(); var vis new bool[nums.Length]; dfs(nums, 0, t, vis, ans); return ans; } private void dfs(int[] nums, int i, IListint t, bool[] vis, IListIListint ans) { if (i nums.Length) { ans.Add(new Listint(t)); return; } for (int j 0; j nums.Length; j) { if (!vis[j]) { vis[j] true; t.Add(nums[j]); dfs(nums, i 1, t, vis, ans); t.RemoveAt(t.Count - 1); vis[j] false; } } } }实现要点与 Java 版本同构动态Listint t配合Add/RemoveAt(t.Count - 1)完成填数与撤销辅助函数dfs把状态作为参数显式传递属于 C# 方法式写法收集结果同样采用new Listint(t)拷贝。五、八种实现的关键差异速查将上面 8 份实现横向对比可以提炼出三个维度的差异理解它们有助于你按语言风格灵活改写语言结果快照方式排列槽位形态撤销动作Pythont[:]切片拷贝定长 list 按索引赋值仅复位vis[j]Javanew ArrayList(t)动态 Listadd/removeremove尾部 复位vis[j]Cemplace_back(t)拷贝构造定长 vector 按索引赋值仅复位vis[j]Goslices.Clone(t)定长 slice 按索引赋值仅复位vis[j]TypeScript / JavaScriptt.slice()定长数组按索引赋值仅复位vis[j]Rustt.clone()定长 Vec 按索引赋值仅复位vis[j]C#new Listint(t)动态 ListAdd/RemoveAtRemoveAt尾部 复位vis[j]共性结论所有语言都必须对存入答案的排列做一次拷贝切片、Clone 或构造副本否则回溯撤销会连带破坏已保存的结果凡使用定长槽位的语言撤销时只需还原vis标记而使用动态容器的语言还需额外弹出尾部元素。这两条规律适用于一切回溯 结果收集类问题。六、复杂度分析设数组长度为 $n$时间复杂度$O(n \times n!)$。排列总数恰好为 $n!$而每构造一个排列从根到叶子需要经历 $n$ 层选择、每层做常数时间的标记与赋值因此总代价为 $n! \times n$。结合约束 $n \le 6$最坏情况 $6 \times 720 4320$ 次基本操作轻松通过。空间复杂度$O(n)$不计输出数组。递归深度最大为 $n$调用栈占用 $O(n)$标记数组vis与槽位数组t各占 $O(n)$答案数组ans属于输出本身不计入辅助空间。七、延伸阅读去重变体「47. 全排列 II」本题所有整数互不相同的约束是回溯得以简化的重要前提。当数组包含重复数字时问题升级为 47. 全排列 II英文版见 README_EN.md要求返回所有不重复的全排列。仓库对 47 题的解法是「排序 回溯」先对nums排序使相同值相邻然后在每一层跳过前一个相同值尚未使用的候选核心去重条件为if vis[j] or (j and nums[j] nums[j - 1] and not vis[j - 1]): continue该条件保证同一层中每个相同值只被选择一次从而在搜索过程中直接剪枝避免了先生成全部排列再用集合去重的低效做法。两题对比可清晰看到从 46 到 47只需在 46 的回溯框架上增加排序 同层去重两步这正是回溯算法框架不变、剪枝条件变化的典型演进路径强烈建议对照学习。两题在仓库总索引 solution/README.md 中相邻收录第 59、60 行便于定位与检索。八、总结LeetCode 46「全排列」是回溯算法入门的第一梯队经典题doocs/leetcode 仓库为它提供了 8 种语言的完整实现。本文围绕其核心骨架——dfs(i)按位填数、vis[]标记已用、递归触底快照、回溯撤销——逐语言拆解了实现差异。掌握本题后你可以将同一套范式迁移到组合总和39、子集78、括号生成22、N 皇后51等大量回溯题目中而面对含重复元素的变体时参考 47 题的排序 同层去重即可快速适配。赞分享示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐LeetCode 46. 全排列题解回溯算法DFS深度剖析与多语言实现LeetCode 46. 全排列题解回溯算法DFS深度剖析与多语言实现 导读 本文基于开源仓库 doocs/leetcode 中 46. 全排列 http示例工程OCRmyPDF 离线安装实战断网环境下为扫描 PDF 补上可搜索文本层OCRmyPDF 离线安装实战断网环境下为扫描 PDF 补上可搜索文本层 生产服务器与外网完全隔离扫描件却天天要归档成可搜索 PDF。OCRmyPDF 离线OCRCLILeetCode 46 全排列Permutations回溯算法深度解析从解题公式到多语言实现LeetCode 46 全排列Permutations回溯算法深度解析从解题公式到多语言实现 本文以开源仓库 leetcodeLeetCode Solu文档教程知识库上一篇西工大软院课程资料大对比为什么nwpu-cram是你的最佳选择下一篇如何扩展commonmark-java自定义节点类型与解析器开发创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
