上一篇是不含重复数字的数组全排列，这篇是有重复数字的数组全排列，要判断得多一点
目录
题目
有重复项数字的全排列（递归回溯，js解法）
解决
代码
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param num int整型一维数组
* @return int整型二维数组
*/
function permuteUnique(num) {
// write code here
num = num.sort((a, b) => a - b); //排序
let len = num.length;
let res = [];
let path = []; //临时排列的数组
let used = []; //使用过的数组
function dg(num) {
if (path.length === len) {
return res.push(path.slice());
}
for (let i = 0; i < len; i++) {
if (i > 0 && num[i] == num[i - 1] && !used[i - 1]) {
//当前的元素num[i]与同一层的前一个元素num[i-1]相同并且num[i-1]已经用过
continue;
}
if (!used[i]) {
//元素未被使用
path.push(num[i]);//元素加到临时数组
used[i] = true; //标记为使用过
dg(num);
path.pop(); //回溯
used[i] = false; //不同层
}
}
}
dg(num);
return res;
}
module.exports = {
permuteUnique: permuteUnique,
};
详情
这个函数使用了回溯算法来实现这一目标。这个函数接受一个参数num，它是一个可能包含重复数字的数组，包含要生成排列的数字。
变量初始化以及排序
num = num.sort((a, b) => a - b); // 排序
let len = num.length;
let res = [];
let path = []; // 临时排列的数组
let used = []; // 使用过的数组- 首先，对输入数组
num进行升序排序，这是为了确保生成的排列是按照字典序排列的。 len变量存储数组num的长度。res数组用于存储所有生成的唯一排列。path数组用于构建当前的排列。used数组是一个布尔数组，用于跟踪哪些元素已经被添加到当前的path中。
递归函数dg
function dg(num) {
// ...
}dg是一个递归函数，用于生成排列。它接受一个参数num，这是当前要处理的数组（实际上是原始数组的一个引用，因为在函数外部已经对它进行了排序）。
递归终止条件
if (path.length === len) {
return res.push(path.slice());
}当path的长度等于输入数组num的长度时，意味着一个完整的排列已经生成。此时，将该排列（path的一个副本）添加到结果数组res中。
递归主体和去重
for (let i = 0; i < len; i++) {
if (i > 0 && num[i] == num[i - 1] && !used[i - 1]) {
// 当前的元素num[i]与同一层的前一个元素num[i-1]相同并且num[i-1]没有用过
// 这意味着如果现在选择num[i]，将会生成一个与之前相同的排列
// 因此，跳过这个元素，以避免生成重复的排列
continue;
}
if (!used[i]) {
// 元素未被使用
path.push(num[i]); // 元素加到临时数组
used[i] = true; // 标记为使用过
dg(num); // 递归调用，继续生成排列
path.pop(); // 回溯，移除刚刚添加的元素
used[i] = false; // 标记为未使用，以便在后续的迭代中可以再次选择它
}
}这个循环遍历数组num的每个元素。
对于每个元素，首先检查它是否与前一个元素相同，并且前一个元素是否没有被使用过。如果是这种情况，那么跳过当前元素，以避免生成重复的排列。
否则，如果元素未被使用（used[i]为false），则将其添加到path中，标记为已使用，递归调用dg函数继续生成排列，然后回溯（移除刚刚添加的元素，并将其标记为未使用）。
初始调用和返回结果
dg(num);
return res;- 初始时，调用
dg函数开始生成排列。 - 最后，返回结果数组
res，它包含了所有生成的唯一排列。
加油加油^_^