LeetCode47

LeetCode47 目录 题目描述示例思路分析代码段代码逐行讲解复杂度分析总结的知识点整合总结

---

题目描述

给定一个可包含重复数字的整数数组 nums，按任意顺序返回所有不重复的全排列。

---

示例 示例 1

输入:

nums = [1, 1, 2]

输出:

[ [1, 1, 2], [1, 2, 1], [2, 1, 1] ]

---

示例 2

输入:

nums = [1, 2, 3]

输出:

[ [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1] ]

---

思路分析 问题核心

我们需要找到数组中所有不重复的全排列。由于数组可能包含重复数字，因此需要避免生成重复的排列。

思路拆解 排序： 将数组排序，使相同的数字相邻，方便后续去重。 深度优先搜索（DFS）： 使用 DFS 遍历所有可能的排列。 剪枝： 在 DFS 过程中，如果当前数字与前一个数字相同，并且前一个数字未被使用，则跳过当前数字，避免重复排列。 回溯： 在 DFS 过程中，使用 visited 数组标记已使用的数字，并在回溯时取消标记。

---

代码段 class Solution { public List<List<Integer>> permuteUnique(int[] nums) { Arrays.sort(nums); List<List<Integer>> res = new ArrayList<>(); dfs(nums, new boolean[nums.length], new LinkedList<>(), res); return res; } private static void dfs(int[] nums, boolean[] visited, LinkedList<Integer> stack, List<List<Integer>> res) { if (stack.size() == nums.length) { res.add(new ArrayList<>(stack)); return; } for (int i = 0; i < nums.length; i++) { if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) { continue; } if (!visited[i]) { stack.push(nums[i]); visited[i] = true; dfs(nums, visited, stack, res); visited[i] = false; stack.pop(); } } } }

---

代码逐行讲解 1. 排序 Arrays.sort(nums); 将数组排序，使相同的数字相邻，方便后续去重。

---

2. 初始化结果列表 List<List<Integer>> res = new ArrayList<>(); res 用于存储所有不重复的排列。

---

3. 调用 DFS dfs(nums, new boolean[nums.length], new LinkedList<>(), res); 调用 DFS 函数，传入数组 nums、visited 数组（用于标记已使用的数字）、stack（用于存储当前排列）和结果列表 res。

---

4. DFS 函数 private static void dfs(int[] nums, boolean[] visited, LinkedList<Integer> stack, List<List<Integer>> res) { DFS 函数的定义，用于递归生成排列。

---

5. 找到一个排列 if (stack.size() == nums.length) { res.add(new ArrayList<>(stack)); return; } 如果当前排列的长度等于数组长度，说明找到一个完整的排列，将其加入结果列表。

---

6. 遍历数组 for (int i = 0; i < nums.length; i++) { 遍历数组中的每个数字，尝试将其加入当前排列。

---

7. 剪枝：避免重复排列 if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) { continue; } 如果当前数字与前一个数字相同，并且前一个数字未被使用，则跳过当前数字，避免重复排列。

---

8. 加入当前数字 if (!visited[i]) { stack.push(nums[i]); visited[i] = true; 如果当前数字未被使用，将其加入当前排列，并标记为已使用。

---

9. 递归 dfs(nums, visited, stack, res); 递归调用 DFS，继续生成下一个数字的排列。

---

10. 回溯 visited[i] = false; stack.pop(); 回溯时取消当前数字的标记，并将其从当前排列中移除。

---

复杂度分析 时间复杂度 全排列的数量为 O(n!)，其中 n 是数组的长度。每次生成一个排列需要 O(n) 的时间。因此，总时间复杂度为 O(n * n!)。 空间复杂度 需要存储所有排列，空间复杂度为 O(n * n!)。递归栈的深度为 n，因此额外空间复杂度为 O(n)。

---

总结的知识点 1. 排序 使用 Arrays.sort 对数组进行排序，方便后续去重。 2. 深度优先搜索（DFS） 使用 DFS 遍历所有可能的排列。 3. 剪枝 在 DFS 过程中，通过条件判断避免生成重复的排列。 4. 回溯 在 DFS 过程中，使用 visited 数组标记已使用的数字，并在回溯时取消标记。

---

整合 class Solution { public List<List<Integer>> permuteUnique(int[] nums) { Arrays.sort(nums); // 排序 List<List<Integer>> res = new ArrayList<>(); // 结果列表 dfs(nums, new boolean[nums.length], new LinkedList<>(), res); // DFS return res; } private static void dfs(int[] nums, boolean[] visited, LinkedList<Integer> stack, List<List<Integer>> res) { if (stack.size() == nums.length) { // 找到一个排列 res.add(new ArrayList<>(stack)); return; } // 遍历 nums 数组 for (int i = 0; i < nums.length; i++) { // 剪枝：避免重复排列 if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) { continue; } if (!visited[i]) { // 如果当前数字未被使用 stack.push(nums[i]); // 加入当前排列 visited[i] = true; // 标记为已使用 dfs(nums, visited, stack, res); // 递归 visited[i] = false; // 回溯 stack.pop(); // 移除当前数字 } } } }

---

总结

这段代码通过排序、DFS 和剪枝，能够高效地生成所有不重复的全排列。