千问 LeetCode 46. 全排列 Java实现

LeetCode 46. 全排列的 Java 实现核心思路是使用经典的回溯算法Backtracking。算法思路全排列问题可以看作是一棵决策树的深度优先遍历DFS。路径Path记录当前已经做出的选择即当前正在生成的排列。选择列表数组中的所有元素。结束条件当路径的长度等于数组的长度时说明一个完整的排列已经生成将其加入结果集。剪枝/避免重复由于每个元素只能使用一次我们需要一个 boolean[] used 数组来记录哪些元素已经被加入了当前路径。回溯的核心逻辑做出选择将元素加入路径标记为已使用。递归进入下一层。撤销选择从路径中移除元素标记为未使用以便尝试其他分支。Java 代码实现class Solution {ListList res new LinkedList();public ListListInteger permute(int[] nums) { // 记录当前路径 LinkedListInteger path new LinkedList(); // 记录元素是否已被使用 boolean[] used new boolean[nums.length]; backtrack(nums, path, used); return res; } private void backtrack(int[] nums, LinkedListInteger path, boolean[] used) { // 触发结束条件路径长度等于数组长度说明找到了一个完整的排列 if (path.size() nums.length) { // 注意Java 中必须 new 一个新的 ArrayList 加入结果集 // 因为 path 是引用传递后续回溯会修改 path 的内容 res.add(new ArrayList(path)); return; } for (int i 0; i nums.length; i) { // 如果当前元素已经在路径中跳过 if (used[i]) { continue; } // 1. 做出选择 path.add(nums[i]); used[i] true; // 2. 进入下一层决策树 backtrack(nums, path, used); // 3. 撤销选择回溯 path.removeLast(); used[i] false; } }}复杂度分析维度 复杂度 说明时间复杂度 O(n times n!) 共有 n! 个排列生成每个排列需要 O(n) 的时间复制路径到结果集空间复杂度 O(n) 递归调用栈的深度为 nused 数组和 path 的空间也是 O(n)不计结果集的空间关键细节与易错点深拷贝问题在将 path 加入 res 时绝对不能直接写 res.add(path)。因为 path 是一个引用在后续的回溯过程中path 会被不断修改元素被移除最终 res 里存的全是空列表。必须使用 new ArrayList(path) 进行深拷贝。数据结构的选择在路径 path 的选择上推荐使用 LinkedList。因为回溯时需要频繁在尾部添加和删除元素LinkedList 的 addLast() 和 removeLast() 都是 O(1) 操作而 ArrayList 的删除操作可能会触发数组元素的移动。与 LeetCode 47含重复元素的全排列的区别本题的前提是数组元素互不相同因此只需要用 used 数组防止同一分支重复使用即可。如果包含重复元素还需要在排序后增加额外的剪枝逻辑if (i 0 nums[i] nums[i-1] !used[i-1]) continue;。需要我顺带把这道题的 Python 或 Golang 版本也写出来吗