前端面试笔试（五）
最近面试中手撕题以及笔试中总遇到递归回溯类题目，于是去牛客上找典型题目。这里浅浅列一道。
目录
题目
解决
代码
详情
变量初始化
递归函数dg
递归终止条件
递归主体
初始调用和返回结果
题目
没有重复项数字的全排列（递归回溯，js解法）
解决
代码
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param num int整型一维数组
* @return int整型二维数组
*/
function permute( num ) {
// write code here
let len=num.length;
let res=[];
function dg(path){
if(path.length===len){
return res.push(path.slice());
}
for(let i=0;i<len;i++){
if(path.indexOf(num[i])===-1){
path.push(num[i]);
dg(path);
path.pop();
}
}
}
dg([]);
return res;
}
module.exports = {
permute : permute
};详情
这个函数使用了回溯算法来实现这一目标。这个函数接受一个参数num，它是一个数组，包含要生成排列的数字。
变量初始化
let len = num.length;
let res = [];len变量存储输入数组num的长度。res数组用于存储所有生成的排列。
递归函数dg
function dg(path) {
// ...
}dg是一个递归函数，用于生成排列。它接受一个参数path，这是一个临时数组，用于构建当前的排列。
递归终止条件
if (path.length === len) {
return res.push(path.slice());
}当path的长度等于输入数组num的长度时，意味着一个完整的排列已经生成。此时，将该排列（path的一个副本，使用path.slice()创建）添加到结果数组res中。
递归主体
for (let i = 0; i < len; i++) {
if (path.indexOf(num[i]) === -1) {
path.push(num[i]);
dg(path);
path.pop();
}
}这个循环遍历输入数组num的每个元素。对于每个元素，如果它还没有被添加到当前的path中（使用path.indexOf(num[i]) === -1检查），则执行以下步骤：
- 将该元素添加到
path中。 - 递归调用
dg函数，继续生成排列。 - 从
path中移除刚刚添加的元素（回溯），以便在下一次循环中尝试其他可能的元素组合。
初始调用和返回结果
dg([]);
return res;- 初始时，以一个空数组作为
path调用dg函数，开始生成排列。 - 最后，返回结果数组
res，它包含了所有生成的排列。
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
加油加油^_^