47. 全排列 II（JS实现）

1 题目
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]

2 思路
这道题主要是运用回溯和剪枝的方法递归地构造一棵树，在递归过程中，存储索引值用于排除已经选取过的数，值得注意的是，假若有多个个相同值的数都没有被选取，我们只能选取一次，其余相同的数直接跳过，否则就会产生重复

3代码
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permuteUnique = function(nums) {
let len = nums.length;
if (len === 0) return [];
if (len === 1) return [nums];

nums.sort((a,b)=>a-b);

const result = [];

for (let i=0; i<len; i++) {
if (i > 0 && nums[i-1] === nums[i]) continue;
d([i]);
}

return result;

function d(arr) {
if (arr.length === len) {
result.push(arr.map(item => nums[item]));
return;
}

for (let i=0; i<len; i++) {
if (arr.includes(i)) continue; //排除已经选取的数
if (i > 0 && nums[i] === nums[i – 1] && !arr.includes(i – 1)) continue; //排除索引不同但值相同的数
let temp = arr.slice();
temp.push(i)
d(temp);
}
}

};