83. 没有重复元素集合的全排列
83. 没有重复元素集合的全排列
题目
给定一个不含重复数字的整数数组 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
中的所有整数 互不相同
注意
本题与 LeetCode 第 46 题 相同。
解题思路
这是一个经典的回溯问题,可以通过深度优先搜索(DFS)来解决。
- 使用一个数组
used
来标记数字是否已经被使用过,确保每个数字在排列中只使用一次,初始时都为false
。 - 定义一个
backtrack
函数,用于搜索所有可能的排列。在函数中进行如下操作:- 如果当前排列的长度等于输入序列的长度,说明已经得到一个完整的排列,将其添加到结果数组中。
- 否则,遍历输入序列的每个数字,如果当前数字没有被使用过,就将其加入当前排列中,并标记为已使用。
- 然后递归调用
backtrack
函数,继续搜索下一个位置的数字。 - 在递归完成后,需要回溯,即将当前数字从排列中移除,并标记为未使用,使其可以在其他位置被使用。
- 最后返回结果数组。
复杂度分析
- 时间复杂度:
O(n * n!)
,其中n
是nums
的长度。主要由递归调用栈的深度决定,递归深度(即排列的数量n!
)乘以每次操作的时间复杂度O(n)
,总时间复杂度为O(n * n!)
。 - 空间复杂度:
O(n * n!)
,空间复杂度主要由以下几个部分组成:- 结果数组
res
用于存储所有生成的唯一排列,在最坏情况下(所有元素都不相同),生成的排列数为n!
,因此结果数组的空间复杂度为O(n * n!)
; - 临时数组
track
,在每个递归调用中,track
的最大长度为n
,因此其空间复杂度为O(n)
; - 布尔数组
used
用于标记哪些元素已经被使用,大小为n
,因此占用O(n)
的空间。 - 综合考虑,最主要的空间复杂度来源于结果数组
res
,因此整体空间复杂度为O(n * n!)
。
- 结果数组
代码
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function (nums) {
const n = nums.length;
let res = [];
let used = new Array(n).fill(false);
const backtrack = (track) => {
if (track.length == n) {
res.push([...track]);
return;
}
for (let i = 0; i < n; i++) {
if (used[i]) {
continue;
}
// 做选择
track.push(nums[i]);
used[i] = true;
// 递归
backtrack(track);
// 撤销选择,回溯
track.pop();
used[i] = false;
}
};
backtrack([]);
return res;
};