最近面试中手撕题以及笔试中总遇到递归回溯类题目，于是去牛客上找典型题目。这里浅浅列一道。

目录

题目

 解决

代码

 详情

变量初始化

递归函数dg

递归终止条件

递归主体

初始调用和返回结果

---

---

题目

没有重复项数字的全排列（递归回溯，js解法）

 解决

代码

javascript">/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param num int整型一维数组 * @return int整型二维数组*/
function permute( num ) {// write code herelet 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，它是一个数组，包含要生成排列的数字。

变量初始化

javascript">let len = num.length;
let res = [];

• len变量存储输入数组num的长度。
• res数组用于存储所有生成的排列。

递归函数dg

javascript">function dg(path) {// ...
}

dg是一个递归函数，用于生成排列。它接受一个参数path，这是一个临时数组，用于构建当前的排列。

递归终止条件

javascript">if (path.length === len) {return res.push(path.slice());
}

当path的长度等于输入数组num的长度时，意味着一个完整的排列已经生成。此时，将该排列（path的一个副本，使用path.slice()创建）添加到结果数组res中。

递归主体

javascript">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检查），则执行以下步骤：

1. 将该元素添加到path中。
2. 递归调用dg函数，继续生成排列。
3. 从path中移除刚刚添加的元素（回溯），以便在下一次循环中尝试其他可能的元素组合。

初始调用和返回结果

javascript">dg([]);
return res;

• 初始时，以一个空数组作为path调用dg函数，开始生成排列。
• 最后，返回结果数组res，它包含了所有生成的排列。

---

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

---

加油加油^_^