题目描述
image
解题思路
在写代码之前，思考以下3个问题：
- 如何判断是否已经满足结束条件？
- 如何在选择列表中选择一个？
- 如何撤销选择？
对全排列这个问题进行具体分析，逐一击破：
1、如何判断是否已经满足结束条件？
显然，每一种全排列的长度 与 题目给定的数组长度一致
因此，只需要比较路径的长度 与 题目给定的数组长度即可
2、如何在选择列表中选择一个？
从广义上说，选择列表就是题目给的数组
从狭义上说，因为题目要求“没有重复”，所以我们需要在选择列表中 剔除那些 已经被包含在路径中的
所以我们就用Set来标记当前路径中存在的元素（保证O(1)的时间复杂度）
每选择一个，就将其加入路径和Set中
3、如何撤销选择？
很简单，从路径中 以及 从Set中删除它即可
代码实现(JavaScript)
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function(nums) {
const res = new Array()
const used = new Set()
var dfs = function(path) {
if(path.length === nums.length){
res.push(path.slice())
return
}
for(let i=0;i<nums.length;i++){
if(used.has(nums[i])){
continue
}
path.push(nums[i])
used.add(nums[i])
dfs(path)
path.pop()
used.delete(nums[i])
}
}
dfs([])
return res
};
