回溯-排列
解题思路
一个数字不能重复地被选，不能产生重复的排列，重复的排列是怎么产生的？
- 比如在横向搜索时 [1,1,2] 先选第一个 1 ，和先选第二个 1 ，往后的情况是一样的；
- 即 同一层 的选项出现重复，或者说当前可选的选项出现重复；
重复的选项要修剪掉，为了方便在迭代中识别出重复，先对 nums 中数字升序排序，使得相同的数字相邻，再利用 used 数组记录 nums 中的元素是佛否被使用过，对使用过的元素要进行剪枝；
图解
代码实现
function backtrack(res, path, used: boolean[], nums): void {
if (path.length === nums.length) {
res.push([...path]);
return;
}
for (let i = 0; i < nums.length; i++) {
// 这个数使用过了，跳过，对当前位去重
if (nums[i] === nums[i - 1] && used[i - 1]) continue;
// 这个数没有被使用过（当前位还未被标记）
if (!used[i]) {
used[i] = true;
path.push(nums[i]);
backtrack(res, path, used, nums);
path.pop();
used[i] = false;
}
}
}
function permuteUnique(nums: number[]): number[][] {
// 数字有重复，排列之后就不会重复
nums.sort((a, b) => b - a);
let list: number[][] = [];
let path: number[] = [];
let used: boolean[] = []; // 记录路径上做过的选择
backtrack(list, path, used, nums);
return list;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 46. 全排列
上一篇
评论
