知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 02 - 全排列 ## 题目(LeetCode 46) 给定一个不含重复数字的数组 nums,返回其所有可能的全排列。 ``` 输入:[1, 2, 3] 输出:[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]] ``` ## 大白话理解 三个坑位,三个数字,每个坑位选一个没用过的数字填进去。 ``` 第 1 个坑位:可以选 1、2、3 第 2 个坑位:可以选剩下的 2 个 第 3 个坑位:只剩 1 个,没得选 就像排队:3 个人排队,有几种排法?3! = 6 种 ``` ## 决策树 ``` [] / | \ [1] [2] [3] / \ / \ / \ [1,2] [1,3] [2,1] [2,3] [3,1] [3,2] | | | | | | [1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1] ``` ## 代码 ```java class Solution { private List<List<Integer>> result = new ArrayList<>(); public List<List<Integer>> permute(int[] nums) { boolean[] used = new boolean[nums.length]; backtrack(nums, new ArrayList<>(), used); return result; } private void backtrack(int[] nums, List<Integer> path, boolean[] used) { // 终止条件:路径长度等于数组长度,说明填满了 if (path.size() == nums.length) { result.add(new ArrayList<>(path)); // 注意要 new 一份 return; } for (int i = 0; i < nums.length; i++) { if (used[i]) continue; // 已经用过了,跳过 path.add(nums[i]); // 做选择 used[i] = true; backtrack(nums, path, used); // 递归 path.remove(path.size() - 1); // 撤销选择 used[i] = false; } } } ``` ### 为什么要 `new ArrayList<>(path)`? path 是一个引用,如果直接 `result.add(path)`,后续的修改会影响已经加入 result 的结果。必须拷贝一份快照。 ### 为什么排列问题每次从 0 开始循环? 因为排列有顺序,`[1,2]` 和 `[2,1]` 是不同的。所以每次都要从头扫描,只跳过已经用过的。 ## 变体:全排列 II(LeetCode 47)— 有重复元素 ``` 输入:[1, 1, 2] 输出:[[1,1,2], [1,2,1], [2,1,1]](不能有重复排列) ``` ```java public List<List<Integer>> permuteUnique(int[] nums) { Arrays.sort(nums); // 先排序,让相同的元素相邻 boolean[] used = new boolean[nums.length]; backtrack(nums, new ArrayList<>(), used); return result; } private void backtrack(int[] nums, List<Integer> path, boolean[] used) { if (path.size() == nums.length) { result.add(new ArrayList<>(path)); return; } for (int i = 0; i < nums.length; i++) { if (used[i]) continue; // 去重:同一层中,相同的数只用第一个 if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; path.add(nums[i]); used[i] = true; backtrack(nums, path, used); path.remove(path.size() - 1); used[i] = false; } } ``` ### 去重逻辑怎么理解? ``` nums = [1a, 1b, 2](a 和 b 区分两个 1) 不去重会产生:[1a,1b,2] 和 [1b,1a,2],本质相同 去重规则:如果 nums[i] == nums[i-1] 且 nums[i-1] 没被使用 → 说明 nums[i-1] 在当前层已经被选过又撤销了 → nums[i] 和它一样,再选就重复了,跳过 简单记:同一层,相同的数只选第一个 ``` ## 复杂度 - 时间:O(n! × n) - 空间:O(n),递归栈 + path + used ## 一句话总结 排列 = 每次从头选 + used 标记。有重复元素就先排序,同一层跳过相同的。 --- 上一篇:[01 - 回溯模板](./01-backtrack-template.md) | 下一篇:[03 - 子集](./03-subsets.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入