.jpg)
612 字
3 分钟
全排列
题目描述
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
解题思路
- 回溯算法框架：
- 维护当前路径
path和结果集res - 遍历未使用元素，依次加入路径
- 递归探索下一层决策
- 回溯时移除最后选择的元素
- 维护当前路径
- 使用状态标记：
- 使用
used数组记录元素使用状态 - 避免同一元素重复使用
- 使用
- 终止条件：
- 路径长度等于原数组长度时保存结果
- 决策空间：
- 每层递归可选择的元素为未使用元素
- 决策树深度等于数组长度
关键洞察
- 决策树结构：
- 根节点为空路径
- 每层扩展所有未使用元素
- 叶子节点为完整排列
- 状态回溯机制：
- 递归返回时恢复
used状态 - 路径数组
pop()撤销选择
- 递归返回时恢复
- 无重复保证：
- 数组不含重复元素自然无重复排列
- 若有重复需额外去重（本题无需）
- 路径独立性：
- 每个递归层级维护独立路径副本
- 回溯时共享同一数组引用
复杂度分析
| 指标 | 说明 |
|---|---|
| 时间复杂度 | O(n × n!)：存在 n! 种排列，生成每个排列需 O(n) 时间（递归树有 n! 叶子节点） |
| 空间复杂度 | O(n)：递归栈深度 O(n) + used 数组 O(n) + 路径数组 O(n) |
注：n 为输入数组长度，n! 为排列总数
| 方法 | 时间复杂度 | 空间复杂度（额外） | 结果顺序 |
|---|---|---|---|
| 回溯+标记 | O(n × n!) | O(n) | 自然顺序 |
| 原地交换 | O(n × n!) | O(1) | 非字典序 |
代码实现
原地交换
/** * @param {number[]} nums * @return {number[][]} */var permute = function (nums) { const result = [];
const dfs = (nums, x) => { if (x === nums.length - 1) { result.push(Array.from(nums)); return; } for (let i = x; i < nums.length; i++) { [nums[i], nums[x]] = [nums[x], nums[i]]; dfs(nums, x + 1); [nums[i], nums[x]] = [nums[x], nums[i]]; } } dfs(nums, 0); return result;};回溯+标记
/** * @param {number[]} nums * @return {number[][]} */var permute = function (nums) { const result = [];
const dfs = (item, visited) => { if (item.length === nums.length) { result.push(item); return; } for (let i = 0; i < nums.length; i++) { if (visited[i] === 0) { visited[i] = 1; dfs([...item, nums[i]], visited); visited[i] = 0; } } }
const visited = new Array(nums.length).fill(0);
for (let i = 0; i < nums.length; i++) { if (visited[i] === 0) { visited[i] = 1; dfs([nums[i]], visited); visited[i] = 0; } }
return result;}