企业官网建设流程全解析

LeetCode 46. 全排列的 Java 实现，核心思路是使用经典的回溯算法（Backtracking）。

算法思路

全排列问题可以看作是一棵决策树的深度优先遍历（DFS）。

1. 路径（Path）：记录当前已经做出的选择（即当前正在生成的排列）。
2. 选择列表：数组中的所有元素。
3. 结束条件：当路径的长度等于数组的长度时，说明一个完整的排列已经生成，将其加入结果集。
4. 剪枝/避免重复：由于每个元素只能使用一次，我们需要一个 boolean[] used 数组来记录哪些元素已经被加入了当前路径。

回溯的核心逻辑：

• 做出选择（将元素加入路径，标记为已使用）。
• 递归进入下一层。
• 撤销选择（从路径中移除元素，标记为未使用），以便尝试其他分支。

Java 代码实现

class Solution {
List<List> res = new LinkedList<>();

public List<List<Integer>> permute(int[] nums) { // 记录当前路径 LinkedList<Integer> path = new LinkedList<>(); // 记录元素是否已被使用 boolean[] used = new boolean[nums.length]; backtrack(nums, path, used); return res; } private void backtrack(int[] nums, LinkedList<Integer> 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) 递归调用栈的深度为 n，used 数组和 path 的空间也是 O(n)（不计结果集的空间）

关键细节与易错点

1. 深拷贝问题：
   在将 path 加入 res 时，绝对不能直接写 res.add(path)。因为 path 是一个引用，在后续的回溯过程中，path 会被不断修改（元素被移除），最终 res 里存的全是空列表。必须使用 new ArrayList<>(path) 进行深拷贝。
2. 数据结构的选择：
   在路径 path 的选择上，推荐使用 LinkedList。因为回溯时需要频繁在尾部添加和删除元素，LinkedList 的 addLast() 和 removeLast() 都是 O(1) 操作，而 ArrayList 的删除操作可能会触发数组元素的移动。
3. 与 LeetCode 47（含重复元素的全排列）的区别：
   本题的前提是数组元素互不相同，因此只需要用 used 数组防止同一分支重复使用即可。如果包含重复元素，还需要在排序后增加额外的剪枝逻辑（if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;）。

需要我顺带把这道题的 Python 或 Golang 版本也写出来吗？