1. 题目描述
给定一个 没有重复 数字的序列,返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
2. 解题思路
这个题目很容易理解,就是将数组中的所有数进行全排列,最后输出全排列的结果。
这个应该还是回溯+剪枝的问题,以1为开头的组合为例:
红色部分就是我们需要剪掉的枝。限制条件就是,结果数组不能重复,元素不能重复。
这里我们初始化一个数组arr,当每一次将一个元素放入结果数组中时,就将其在arr中标记为true。这样,下一次在往里面加其他元素时,查找该元素,就可以避免元素的重复。
实际上,JavaScript为我们提供了 find()
方法来查找是否存在某个元素。那为什么我们还要整的这么复杂,用arr来保存数据呢?因为,find()
方法的时间复杂度为O(n),所以我们使用arr来保存已经遍历过的元素。这样就用空间换了时间,降低了时间复杂度。
2. 代码实现
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function(nums) {
const res = [] // 保存最后的结果
const arr = [] // 将这条路径上已有的元素保存为true,避免元素重复
const dfs = (path) => {
if(path.length === nums.length){
res.push([...path])
return
}
for(let num of nums){
if(arr[num]) continue // 如果已经存在这个数,就跳过
path.push(num)
arr[num] = true
dfs(path)
path.pop()
arr[num] = false
}
}
dfs([])
return res
};