原题链接：https://leetcode-cn.com/problems/permutations-ii/
解题思路：
该题是47. 全排列 II的进阶版，在其之上加入了过滤出不重复排列的需求。如果你对[47. 全排列 II](https://leetcode-cn.com/problems/permutations-ii/)的解法不熟悉，可以查看我的题解[LeetCode 题解：46. 全排列，回溯，JavaScript，详细注释](https://leetcode-cn.com/problems/permutations/solution/leetcodeti-jie-46-quan-pai-lie-hui-su-javascriptxi/)。
使用DFS生成所有可能的排列情况。
需要使用 used 数组，标识 nums 中每个值是否被使用过。
清除状态的注意点：
* 由于 permutation 和 used 变量会在每次递归被重复使用，需要注意每次递归后恢复当前状态。
* 假设是第一层递归，for 循环清楚状态后每次得到的 permutation 分别为[1]、[2], [3]， used 分别为[true, false, false]、[false, true, false]、[false, false, true]。
* 也就是说，当 permutation 为[2]时，上一次循环中所有可能的排列情况都已被输出，而且 nums 所有被使用过的状态都被清除，不会影响当前的递归。
过滤重复排列的注意点：
* 将 nums 进行排序，保证每个数字的连续性，一个数字判断完成之后不会重复判断。
* 在递归中遍历数字时，以[1, 1, 2]为例，只有在遍历到第二个1时，才会采用其对应的排列，之前的排列全部都会被过滤掉。
递归终止时，由于 permutation 只是一个引用，即它的值会随着函数的运行不断改变，因此需要将其 copy 一份，否则最终输出的结果都会是[]
function recursion(nums, result, permutation, used) {
// 1. 递归终止条件
// 当排列的结果达到原序列长度时，退出循环
if (permutation.length === nums.length) {
// 将当前排列存入结果，需要将原数组copy一份，否则permutation会在for循环结束后被清空
result.push(permutation.slice());
return;
}
// 利用循环产生不同的排列
// 假设是第一层递归，for循环每次得到的permutation分别为[1], [2], [3]。
// 下一层的递归就在第一层的基础上继续进行
// 由于进入每一层递归时，并不知道上一层的排列情况，只能进行遍历查找。
for (let i = 0; i < nums.length; i++) {
// 2. 当前层的递归逻辑
// 如果当前值已经被使用过，则不可以进行排列，直接跳过
// 最终的效果就是，只有当前值最后一次被遍历到时，才会被使用。
if (
used[i] || // 如果当前值已被排列过
// 由于nums的值可重复，即使used[i]为false，当前值也有可能已被排列过
// 如果相邻两个字相等，表示当前值可能已在前一个值的递归中被排列过
(nums[i] === nums[i - 1] && used[i - 1]) // 判断前一个值是否已被排列过
) {
continue;
}
// 当前值已经进行排列，在used中进行标识
used[i] = true;
// 将当前值存入排列
permutation.push(nums[i]);
// 可以在此处打印当前排列情况，帮助理解
// console.log(result, permutation, used);
// 3. 下探到下一层递归
// 注意此时为深度优先遍历，也就是说recursion完成之后，已经处理完了一种排列的最终结果
recursion(nums, result, permutation, used);
// 4. 恢复当前层状态
// 在当前值被使用过后，将used置为空，提供给下一次for循环使用
used[i] = false;
// 将当前已使用的值从permutation中弹出，避免英下乡下一次循环结果
permutation.pop();
}
}
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permuteUnique = function (nums) {
let result = []; // 存储结果
let permutation = []; // 存储每次排列的结果
let used = new Array(nums.length).fill(false); // 通过index对应的布尔值，标识nums中各个值是否被使用
nums.sort((a, b) => a - b); // 将nums进行排序，保证能否正确去重
// 递归生成全排列
recursion(nums, result, permutation, used);
return result;
};
复制代码
评论 (4 条评论)