--- tags: ["LeetCode", "回溯", "数组", "中等"] create time: 2026-05-17 10:00 --- # 55-全排列 ## 题面 > **LeetCode 46. Permutations** 给定一个不含重复数字的数组 `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` 中的所有整数 **互不相同** --- ## 思路 > [!question] 💡 思考 手动列出 `[1, 2, 3]` 的所有排列——你会怎么列？ 大概率是：先选 1 开头（剩两个位置自由排列），再选 2 开头……每一步从剩余元素中选一个填到当前位置，然后递归处理下一个位置。 这正是回溯算法的经典场景：**枚举一棵决策树的所有完整路径**。 > [!abstract] 🎯 核心洞察 全排列的本质是"从 n 个元素中选 n 个放入序列"，分解为 `n` 层决策： | 决策层 | 任务 | 可选元素 | |--------|------|---------| | 第 1 层 | 选第 1 个位置的数 | 全部 n 个 | | 第 2 层 | 选第 2 个位置的数 | 除去已选的 | | ... | ... | ... | | 第 n 层 | 选最后一个 | 仅剩 1 个 | 每层选择数递减：`n × (n-1) × ... × 1 = n!`，所以时间复杂度必然是 O(n!)。 ### 回溯框架三要素 任何回溯问题都可以归纳为三个操作： ``` 选择 → 递归 → 撤销选择（回溯） ``` - **选择**：做出当前决策，进入下一层。 - **递归**：在已选基础上继续探索。 - **撤销**：回退上一步，尝试其他分支。 维护一个 `path` 记录当前路径，用一个 `used[]` 布尔数组标记哪些元素已被选中——遍历时跳过已用的即可。 ### 回溯决策树（以 `nums = [1, 2, 3]` 为例） ```mermaid flowchart TD root["空 []"] --> L1a["选 1\n[1]"] root --> L1b["选 2\n[2]"] root --> L1c["选 3\n[3]"] L1a --> L2a["选 2\n[1,2]"] L1a --> L2b["选 3\n[1,3]"] L1b --> L2c["选 1\n[2,1]"] L1b --> L2d["选 3\n[2,3]"] L1c --> L2e["选 1\n[3,1]"] L1c --> L2f["选 2\n[3,2]"] L2a --> Leaf1["[1,2,3] ✅"] L2b --> Leaf2["[1,3,2] ✅"] L2c --> Leaf3["[2,1,3] ✅"] L2d --> Leaf4["[2,3,1] ✅"] L2e --> Leaf5["[3,1,2] ✅"] L2f --> Leaf6["[3,2,1] ✅"] classDef leaf fill:#90EE90,stroke:#228B22,color:#000; class Leaf1,Leaf2,Leaf3,Leaf4,Leaf5,Leaf6 leaf; ``` ### 两种实现方式 > [!tip] 🔑 方法一：`used` 数组（⭐ 推荐） 每层从头遍历所有元素，通过 `used[]` 跳过已选。这是最标准的回溯模板，清晰易懂。 > [!note] 🔑 方法二：原地交换（进阶） 交换 `nums[i]` 和 `nums[start]` 等价于"选 nums[i] 放在 start 位置"，递归后恢复交换即撤销。省去了 `used[]` 和 `path[]`，空间更紧凑，但去重时不如方法一方便。**面试中作为加分项**。 **何时用哪种？** | 场景 | 推荐 | |------|------| | 首次学习 / 面试快速写对 | **方法一**（used 数组） | | 面试官追问 O(1) 额外空间 | **方法二**（原地交换） | | 含重复元素的排列（LC 47） | **方法一** + 排序去重 | - **时间复杂度**：O(n × n!) — 共 n! 条完整路径，每条拷贝需 O(n) - **空间复杂度**：O(n) — 递归栈深度 --- ## 代码提示 > [!abstract] 📝 回溯通用骨架 ```go var result [][]int var dfs func(path []int) dfs = func(path []int) { // Base Case: 路径已满 if len(path) == len(nums) { result = append(result, append([]int(nil), path...)) // ⚠️ 必须拷贝 return } for i := 0; i < len(nums); i++ { if used[i] { continue // 剪枝：跳过已选元素 } // 做选择 path = append(path, nums[i]) used[i] = true // 递归 dfs(path) // 撤销选择 used[i] = false path = path[:len(path)-1] } } dfs(nil) return result ``` --- ## 技巧 > [!tip] 🔑 核心模式 全排列是回溯最经典的入门题，掌握后可迁移到大量同类问题： | 问题类型 | 决策方式 | 代表题目 | |---------|---------|---------| | **全排列** | 每层从**全部未用元素**中选 | LC 46（本题） | | **组合** | 每层从**当前及之后**选（不回头） | LC 77 组合 | | **子集** | 每个元素**选或不选** | [[回溯/56-子集]] | > [!step] ⭐ 四步回溯法 ```mermaid flowchart LR S1["① 定义签名
需要什么参数？"] --> S2["② Base case
何时停止？"] S2 --> S3["③ for 循环
有哪些选择？"] S3 --> S4["④ 递归+回溯
选什么？撤什么？"] S4 --> DONE["✅"] ``` > [!danger] ⚠️ 两个常见陷阱 **① Go 切片不拷贝直接存结果**：`path` 指向同一底层数组，不拷贝的话所有结果会被后续回溯覆盖成同一个值。 ```go // ❌ 错误 result = append(result, path) // ✅ 正确：创建独立副本 tmp := make([]int, len(path)) copy(tmp, path) result = append(result, tmp) // ✅ 或者一行搞定 result = append(result, append([]int(nil), path...)) ``` **② 混淆 `for i := range nums` 和 `for i := start; i < len(nums)`**： - `range nums`（从头遍历 + `used[]`）→ 全排列，允许跳到任意未用元素 - `range start`（从当前位置往后）→ 组合/子集，不允许回头以避免重复 --- ## 代码 > [!success] ✅ 方法一：`used` 数组标记（推荐） ```go // permute 返回 nums 的所有全排列（使用 used 数组标记法）。 // // 时间复杂度：O(n * n!) — 共 n! 条完整路径，每条 O(n) 拷贝 // 空间复杂度：O(n) — 递归栈深度为 n func permute(nums []int) [][]int { var result [][]int path := make([]int, 0, len(nums)) used := make([]bool, len(nums)) var dfs func() dfs = func() { if len(path) == len(nums) { tmp := make([]int, len(nums)) copy(tmp, path) result = append(result, tmp) return } for i := 0; i < len(nums); i++ { if used[i] { continue } path = append(path, nums[i]) used[i] = true dfs() used[i] = false path = path[:len(path)-1] } } dfs() return result } ``` > [!success] ✅ 方法二：原地交换 ```go // permuteSwap 使用原地交换实现全排列。 // // 时间复杂度：O(n * n!) // 空间复杂度：O(n) — 仅递归栈开销 func permuteSwap(nums []int) [][]int { var result [][]int var dfs func(start int) dfs = func(start int) { if start == len(nums) { tmp := make([]int, len(nums)) copy(tmp, nums) result = append(result, tmp) return } for i := start; i < len(nums); i++ { nums[start], nums[i] = nums[i], nums[start] dfs(start + 1) nums[start], nums[i] = nums[i], nums[start] // 恢复 } } dfs(0) return result } ``` > [!success] ✅ 单元测试 ```go import ( "slices" "testing" ) func TestPermute(t *testing.T) { tests := []struct { name string input []int expect [][]int }{ {name: "示例1", input: []int{1, 2, 3}, expect: [][]int{{1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}}}, {name: "示例2", input: []int{0, 1}, expect: [][]int{{0,1},{1,0}}}, {name: "单元素", input: []int{1}, expect: [][]int{{1}}}, } for _, tt := range tests { t.Run(tt.name, func(t *testing.T) { got := permute(append([]int{}, tt.input...)) slices.SortFunc(got, func(a, b []int) int { return slices.Compare(a, b) }) slices.SortFunc(tt.expect, func(a, b []int) int { return slices.Compare(a, b) }) if !slices.Equal(got, tt.expect) { t.Errorf("permute(%v) = %v; want %v", tt.input, got, tt.expect) } }) } } ``` > [!quote] 💬 延伸思考 全排列的决策树是一棵**规则的 n 叉树**——叶子节点数 = n!。这也正是信息论下界：你必须至少访问 n! 个叶子才能列出全部排列，所以 O(n·n!) 已是最优。 > [!summary] 📋 本章要点回顾 > 全排列是回溯的最佳入门题： > > 1. **模型简洁**——决策规则对称，便于手绘理解 > 2. **模板通用**——"选择→递归→撤销"可无缝迁移到组合、子集、N 皇后 > 3. **优化阶梯清晰**——从 `used` 数组到原地交换，再到第 K 个排列的数学构造 > > **口诀**：一进一出两改两回，选了加，回去退。 --- > [!example] 🔀 关联变体题 - **LeetCode 47. Permutations II** — 含重复元素的全排列 - **[[回溯/56-子集]]** — 回溯最基础范式，决策树是二叉树（选或不选） - **[[回溯/57-电话号码的字母组合]]** — 多叉树搜索，每层候选集不同 - **[[技巧/99-下一个排列]]** — 有序生成排列，不需要枚举全部