全排列

副标题 / 摘要 如果说子集题教你“组合型回溯”的骨架，那么全排列题教你的就是“状态型回溯”的核心：当前位置要选一个还没用过的元素，直到路径长度等于 n 才收集答案。 预计阅读时长：10~12 分钟 标签：Hot100、回溯、全排列、DFS SEO 关键词：Permutations, 全排列, 回溯, used, DFS 元描述：通过 LeetCode 46 固定排列型回溯模板，重点理解 used[]、叶子收集与多语言实现。 目标读者 已经做完 78. 子集，准备进入排列型回溯的学习者 会写递归，但状态恢复经常出错的开发者 需要枚举任务执行顺序、测试顺序或操作序列的工程师 背景 / 动机 排列问题和组合问题最本质的区别是： 组合只关心“选了哪些元素” 排列还关心“这些元素出现的顺序” 所以在全排列里，[1,2,3] 和 [1,3,2] 是两个不同答案。 这意味着你不能再靠 startIndex 只向后看，而必须显式记录“哪些元素已经用过”。 LeetCode 46 的价值就在这里：它把“状态恢复”这件事讲得非常干净。 核心概念 path：当前构造中的排列 used[i]：nums[i] 是否已经被当前路径使用 叶子收集答案：只有当路径长度等于 nums.length 时，才得到一个完整排列 状态撤销：递归返回时同时撤销 path 和 used A — Algorithm（题目与算法） 题目还原 给定一个不含重复数字的数组 nums，返回它的所有可能全排列。 答案顺序不限。 输入输出 名称 类型 描述 nums int[] 不含重复元素的整数数组 返回 int[][] 所有可能的全排列 示例 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 中所有整数互不相同 C — Concepts（核心思想） 从子集题到全排列题，模板哪里变了 78. 子集 的关键是 startIndex，因为组合不关心顺序。 但全排列不同，每一层都可以从“所有还没用过的元素”里选一个，所以： ...