- 正确答案：给定一个不含重复数字的数组 nums，返回其所有可能的全排列。例如输入 [1,2,3]，输出应为 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]。核心解法是回溯（Backtracking），通过递归+状态重置（路径选择与撤销）生成所有排列。 - 解答思路：全排列的本质是“在每个位置上尝试所有尚未使用过的元素”。我们维护一个路径 path（当前已选序列）和一个布尔数组 used[]（标记 nums[i] 是否已被选）。每次递归中，遍历 nums 所有索引 i，若 !used[i]，则将 nums[i] 加入 path，标记 used[i]=true，进入下一层递归；递归返回后，从 path 弹出 nums[i] 并恢复 used[i]=false（即回溯）。当 path 长度等于 nums 长度时，找到一个合法排列，拷贝加入结果列表。该过程等价于在 n 叉决策树上进行深度优先搜索（DFS），每条从根到叶的路径对应一个排列。 - 深度知识讲解： 1. **回溯算法本质**：回溯是 DFS 在组合/排列/子集问题中的具体应用，其关键在于“做选择→递归→撤销选择”三步闭环。它不同于普通 DFS 的地方在于显式维护和恢复状态（如 used 数组、path 列表），以支持多路径探索。 2. **时间复杂度分析**：全排列总数为 n!，每种排列需 O(n) 时间拷贝（Java 中 ArrayList.clone() 或 Python 中 list.copy()），故总时间复杂度为 O(n × n!)。注意：这不是指数级而是阶乘级，增长极快，体现组合爆炸特性。 3. **空间复杂度**：递归栈深度为 O(n)，每层额外空间 O(n)（用于存储 path 和 used），故空间复杂度为 O(n²)；若忽略结果存储空间，主导项是递归栈 O(n)。 4. **与子集/组合问题的区别**：子集问题关注“选或不选”，无顺序性，用 start 索引避免重复；而全排列强调“顺序”，每个位置都可选任意未用元素，因此必须用 used 数组而非 start 索引来去重（否则会漏掉如 [2,1,3] 这类非升序排列）。 5. **底层数据结构支撑**：ArrayList（Java）或 list（Python）支持 O(1) 尾部增删，适合 path 的 push/pop；布尔数组 used 提供 O(1) 访问和更新，替代哈希集合（HashSet）可避免哈希开销，更高效。 6. **剪枝优化可能性**：本题无约束条件，故无有效剪枝；但若题目扩展为“带限制的排列”（如相邻差值不能为 k），则可在递归前加 if 判断实现剪枝。 7. **迭代解法（非主流但重要）**：可用字典序生成法（Steinhaus-Johnson-Trotter 或 next_permutation 算法），其思想是基于当前排列生成字典序下一个排列，时间复杂度 O(1) 均摊，空间 O(1)，但实现复杂，面试中回溯更考察思维清晰度。 - 伪代码（通用语言描述）： ``` result = [] path = [] used = boolean array of length n, all false function backtrack(): if length(path) == n: add a copy of path to result return for i from 0 to n-1: if not used[i]: append nums[i] to path used[i] = true backtrack() remove last element from path used[i] = false call backtrack() return result ``` - Java 实现（关键细节说明）： ``` public List> permute(int[] nums) { List> result = new ArrayList<>(); List path = new ArrayList<>(); boolean[] used = new boolean[nums.length]; backtrack(nums, path, used, result); return result; } private void backtrack(int[] nums, List path, boolean[] used, List> result) { if (path.size() == nums.length) { result.add(new ArrayList<>(path)); // 必须 new ArrayList<>(path)，否则存的是引用 return; } for (int i = 0; i < nums.length; i++) { if (!used[i]) { path.add(nums[i]); used[i] = true; backtrack(nums, path, used, result); path.remove(path.size() - 1); // 回溯：撤销最后一步选择 used[i] = false; } } } ``` - Python 实现（简洁版）： ``` def permute(self, nums: List[int]) -> List[List[int]]: result = [] path = [] used = [False] * len(nums) def backtrack(): if len(path) == len(nums): result.append(path[:]) # path[:] 创建浅拷贝 return for i in range(len(nums)): if not used[i]: path.append(nums[i]) used[i] = True backtrack() path.pop() # 等价于 remove last used[i] = False backtrack() return result ``` - 扩展知识点： - 若输入含重复元素（LC47），需先排序 + 跳过相同元素的重复选择：在 for 循环中加判断 `if i > 0 and nums[i] == nums[i-1] and not used[i-1]`（保证相同元素按顺序使用，避免重复排列）。 - 迭代版本可基于交换原地生成（C++ STL 的 next_permutation 即采用此法）：从右往左找第一个升序对 (i, i+1)，再从右往左找第一个大于 nums[i] 的 nums[j]，交换后反转 nums[i+1:]。 - 函数式编程视角：全排列可视为对称群 S_n 的全部元素，每个排列是 {0,1,…,n−1} 的双射，其复合运算构成群结构——这解释了为何排列数为 n!（n 个元素的双射总数）。 - 实际应用：密码学中的密钥空间枚举、测试用例生成（如 UI 操作序列）、调度问题（任务执行顺序枚举）等场景均依赖全排列生成能力。

百度-日常实习-推荐算法面经分享

全站热榜

创作者周榜