题解 | #没有重复项数字的全排列#
没有重复项数字的全排列
http://www.nowcoder.com/practice/4bcf3081067a4d028f95acee3ddcd2b1
深度优先遍历+回溯算法
let len = nums.length, result = [], visited = new Array(len).fill(false);
const dfs = (depth, path, visited) => {
// 遍历到叶子结点了，可以返回了
if(depth === len) {
result.push([...path]);
}
for(let i = 0; i < len; i++) {
// 如果没遍历过
if(!visited[i]) {
// 压入 path 数组，然后是否遍历过的数组此下标处变为 true
path.push(nums[i]);
visited[i] = true;
// 继续 dfs，直到最后一层
dfs(depth + 1, path, visited);
// 进行回溯，还原，以便下一次使用
visited[i] = false;
path.pop();
}
}
}
dfs(0, [], visited);
return result;
}
module.exports = {
permute : permute
};
要点
1：将问题想象为状态空间树 -->如何遍历树，得到叶子结点 2：设置状态变量，depth,path,visited.用来记录当前遍历节点的状态 3：递归是在for循环中实现的，注意回溯需要重置状态。递归的出口是当前结果的长度与原数组长度一致。
查看5道真题和解析