leetcode-go/回溯/55-全排列.md

tags, create time

tags	create time
LeetCode 回溯 数组 中等	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] 为例）

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] 📝 回溯通用骨架

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] ⭐ 四步回溯法

flowchart LR
    S1["① 定义签名<br/>需要什么参数？"] --> S2["② Base case<br/>何时停止？"]
    S2 --> S3["③ for 循环<br/>有哪些选择？"]
    S3 --> S4["④ 递归+回溯<br/>选什么？撤什么？"]
    S4 --> DONE["✅"]

[!danger] ⚠️ 两个常见陷阱

① Go 切片不拷贝直接存结果：path 指向同一底层数组，不拷贝的话所有结果会被后续回溯覆盖成同一个值。

// ❌ 错误
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 数组标记（推荐）

// 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] ✅ 方法二：原地交换

// 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] ✅ 单元测试

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-下一个排列 — 有序生成排列，不需要枚举全部