LeetCode 47. 全排列 II的 Java 实现核心思路依然是回溯算法但由于数组中包含重复元素我们需要增加排序和同层剪枝的逻辑来避免生成重复的排列。算法思路排序首先对数组进行排序使得相同的元素在物理位置上相邻。这是进行剪枝的前提。同层去重核心剪枝在回溯的 for 循环中如果当前元素 nums[i] 与前一个元素 nums[i-1] 相同我们需要判断是否应该跳过如果 used[i-1] true说明 nums[i-1] 在当前路径树枝上已经被使用这是合法的不需要跳过。如果 used[i-1] false说明 nums[i-1] 在当前层同一横向分支刚刚被回溯撤销。为了避免生成重复排列例如先选 nums[i] 再选 nums[i-1]和先选 nums[i-1] 再选 nums[i] 是一样的必须跳过当前元素 nums[i]。Java 代码实现class Solution {ListList res new LinkedList();public ListListInteger permuteUnique(int[] nums) { // 1. 必须先排序让相同的元素靠在一起 Arrays.sort(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) { res.add(new ArrayList(path)); return; } for (int i 0; i nums.length; i) { // 如果当前元素已经在路径中跳过 if (used[i]) { continue; } // 2. 核心剪枝同层去重 // 如果当前元素和前一个元素相同且前一个元素在当前层没有被使用即刚被回溯撤销 // 则跳过当前元素避免生成重复排列 if (i 0 nums[i] nums[i - 1] !used[i - 1]) { continue; } // 做出选择 path.add(nums[i]); used[i] true; // 进入下一层 backtrack(nums, path, used); // 撤销选择 path.removeLast(); used[i] false; } }}复杂度分析维度 复杂度 说明时间复杂度 O(n times n!) 最坏情况下无重复元素有 n! 个排列生成每个排列需要 O(n) 时间空间复杂度 O(n) 递归栈深度、used 数组和 path 的空间均为 O(n)不计结果集关键细节与易错点为什么必须排序如果不排序相同的元素可能分散在数组各处nums[i] nums[i-1] 的判断就会失效无法正确剪枝。剪枝条件的理解!used[i-1] 代表的是同层去重。也可以写成 used[i-1] true 时跳过这代表的是同分支去重即保证相同元素的相对顺序不变。这两种写法都能正确去重但同层去重本题采用的写法在大多数情况下效率更高因为它能更早地剪掉整棵重复的子树。与 LeetCode 46 的对比本题仅仅比 46 题多了一行排序和一行 if 判断但考察了对回溯树横向同层与纵向同分支的深刻理解。需要我顺带把这道题的 Python 或 Golang 版本也写出来吗
