047.全排列 II
作者：沉默王二
发布时间：2024-09-14T11:55:46.962+0800
二哥瞎逼逼：转眼间，已经进入到 9 月中旬了，一些球友已经拿到转正意向或者 oc 了，当然更多的球友还在耐心地准备当中。那今天就来刷一道二哥的 LeetCode 刷题笔记醒一下脑子。
题意
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有 不重复 的全排列。
难度
中等
示例
示例 1：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
### 分析
这道题是 046.全排列 的延续。046.全排列 中没有重复数字，但 047 中有重复元素。
但是，nums的元素顺序并不会影响结果，所以我们不妨把元素从小到大排个序。在之前的题解中，我们知道，排序在很多时候可以减少题解的复杂度。
这道题也是一样的，当我们对 nums 进行排序后，就可以保证相同的数字会相邻，方便我们在回溯过程中跳过重复的数字。
好，来看这个例子：nums = [1,1,2]，如果按照 046.全排列 思路的话，我们会得到这样的结果：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
ans = [
[1,1,2],
[1,2,1],
[1,1,2],
[1,2,1],
[2,1,1],
[2,1,1]
]
可以看到，我们得到了重复的结果，但其实我们只要保证同个位置同个元素只被填入一次就可以避免重复，对吧？
然后在回溯和剪枝中，我们使用布尔数组 used 记录哪些元素已经被选中，避免重复使用。
在回溯过程中，如果当前数字与前一个数字相同，并且前一个数字还没有被使用（!used[i-1]），说明在同一层已经选择过该数字，应该跳过这个选择。
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
continue;
}
关于这一点，很容易搞混，为什么是 !used[i-1] 而不是 used[i-1] 呢？
我截个图，debug 的时候就明白了。
当输入是 [1,1,2] 的时候，从第 1 个 1 开始，我们可以得到 [[1(0),1(1),2],[1(0),2,1(1)]]，然后我们回溯到第 2 个 1 的时候，我们需要跳过 1(1),1(0),2 这个选择， 对吧？
ok，我们来看完整的题解。
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
class Solution04701 {
public List<List
List<List
List
boolean[] used = new boolean[nums.length];
// 排序数组，以便剪枝
Arrays.sort(nums);
backtrack(nums, result, path, used);
return result;
}
// 回溯函数
private void backtrack(int[] nums, List<List<Integer>> result, List<Integer> path, boolean[] used) {
// 如果当前排列的长度等于 nums 的长度，说明找到一个完整的排列
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
// 遍历每一个数字，尝试将其加入排列
for (int i = 0; i < nums.length; i++) {
// 剪枝条件：如果当前数字已经被使用，或者与前一个数字相同且前一个数字还未被使用
if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
continue;
}
// 做选择：选择当前数字
path.add(nums[i]);
used[i] = true;
// 继续递归处理剩余数字的排列
backtrack(nums, result, path, used);
// 撤销选择：回溯
path.remove(path.size() - 1);
used[i] = false;
}
}
public static void main(String[] args) {
Solution04701 solution = new Solution04701();
int[] nums = {1, 1, 2};
List<List<Integer>> result = solution.permuteUnique(nums);
System.out.println(result); // 输出所有不重复的全排列
}
}
比起 046，这里只是多了一个排序和一个剪枝操作。
来看一下时间复杂度。
总结
LeetCode 中很多题都是很相似的，尤其是 ② 这种，就是在 ① 的基础上加了一些限制条件。所以，我们在解题的时候，可以先找到一个通用的解法，然后再根据题目的限制条件进行修改。
这道题就是通过回溯和剪枝的方式，找到所有不重复的全排列。
力扣链接：https://leetcode.cn/problems/permutations-ii/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
PDF 版本目前只针对二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 加入我们吧。
一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 6100 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！
语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
这道题可以说完全重写了，给出 1 道大家完全都能掌握的题解（ 主要是理解回溯和剪枝算法的底层逻辑）。
增加代码注释，这样大家更容易看懂并掌握题解；
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
增加手绘图，这样大家更容易理解解题思路；
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。