46. 全排列

46. 全排列

中等

相关标签

给定一个不含重复数字的数组nums，返回其所有可能的全排列。你可以按任意顺序返回答案。

示例 1：

输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1] 输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1] 输出：[[1]]

提示：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums中的所有整数互不相同

📝核心笔记：全排列 (Permutations)

1. 核心思想 (一句话总结)

“N 个萝卜 N 个坑，标记已用，填满为止。”

全排列就是把 N个数字填入 N 个空位中。

我们需要一个 onPath (或者 visited) 数组来记录**“哪些萝卜已经被拔出来了”**，防止一个数字在一个排列中被用两次。

💡图像记忆 (决策树)：

• 第 0 层：有 3 个选择 (1, 2, 3)。选了 1。
• 第 1 层：剩 2 个选择 (2, 3)。选了 2。
• 第 2 层：剩 1 个选择 (3)。选了 3。
• 触底：[1, 2, 3]收集！
• 回溯：退回到第 1 层，把 2 放回去，改选 3...

2. 算法流程 (三步走)

1. 路径与标记 (Init)：

• • path：当前正在构建的排列 (长度固定为)。
  • onPath：记录nums里的每个下标是否已经被选到了path中。

1. 递归填坑 (DFS)：

• • dfs(i)的含义是：现在我们要决定第i个位置填哪个数。
  • 遍历所有候选数字nums[j]，如果!onPath[j](没用过)，就填入。

1. 回溯 (Backtrack)：

• • 做选择：填入数字，标记true。
  • 递归：i + 1，去填下一个坑。
  • 撤销选择：标记false(把萝卜放回原处，给别的分支用)。
  • 注：path的值不需要撤销，因为下次会被新的set覆盖。

🔍代码回忆清单 (带注释版)

// 题目：LC 46. Permutations class Solution { public List<List<Integer>> permute(int[] nums) { int n = nums.length; // 技巧：预先填满 null，后面只用 set 修改，避免频繁 add/remove List<Integer> path = Arrays.asList(new Integer[n]); boolean[] onPath = new boolean[n]; // 记录 nums[j] 是否已使用 List<List<Integer>> ans = new ArrayList<>(); dfs(0, nums, ans, path, onPath); return ans; } // i : 当前正在填第几个坑 (0 ~ n-1) private void dfs(int i, int[] nums, List<List<Integer>> ans, List<Integer> path, boolean[] onPath) { // 1. Base Case: 坑填满了 if (i == nums.length) { //只要你在回溯中复用一个可变的 path 容器，每次收集结果时就必须做 deep copy ans.add(new ArrayList<>(path)); // ⚠️ 必须 Deep Copy (新建一个 List) return; } // 2. 尝试每一个候选数字 for (int j = 0; j < nums.length; j++) { if (!onPath[j]) { // 只有没用过的才能填 // A. 做选择 //把 nums[j] 放到 path 的第 i 个位置上。 path.set(i, nums[j]); onPath[j] = true; // B. 进入下一层 dfs(i + 1, nums, ans, path, onPath); // C. 撤销选择 (回溯) onPath[j] = false; // path.set(i, null) <-- 这句不需要，因为下次循环或者下个分支会直接覆盖它 } } } }

⚡快速复习 CheckList (易错点)

• [ ]结果列表是空的？

• • 99% 是因为忘了new ArrayList<>(path)。
  • 如果直接ans.add(path)，因为path在内存里只有一份，回溯完之后它会变回初始状态，或者被改得乱七八糟。必须拷贝快照。

• [ ]onPath怎么恢复？

• • 必须成对出现：递归前true，递归后false。
  • 如果不置为false，这个数字在回退到上一层后，依然显示“被占用”，导致其他分支无法使用它。

• [ ]对比Swap写法？

• • 还有一种写法是不开onPath数组，直接在nums上交换元素。
  • 你的写法 (boolean数组)：结果是字典序的 (如果输入有序)，更符合人类直觉。
  • Swap 写法：结果顺序是乱的，但省一点点空间。面试推荐你现在的写法，稳。

🖼️数字演练

输入nums = [1, 2, 3]

1. DFS(0): 坑位[?, ?, ?]。

• • 选1(onPath[0]=true) ->[1, ?, ?]-> CallDFS(1)。

1. DFS(1):

• • 选2(onPath[1]=true) ->[1, 2, ?]-> CallDFS(2)。

1. DFS(2):

• • 选3(onPath[2]=true) ->[1, 2, 3]-> CallDFS(3)。

1. DFS(3):

• • i == 3，收集[1, 2, 3]，返回。

1. 回溯到 DFS(2):

• • onPath[2]=false。尝试选别的？没得选了，返回。

1. 回溯到 DFS(1):

• • onPath[1]=false。循环继续，选3...
  • ->[1, 3, ?]...

(最终结果：收集完所有可能)