二哥的 LeetCode 刷题笔记：047.全排列 II
作者：沉默王二
发布时间：2022-10-10T11:13:37.746+0800
047.全排列 II
题意
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有 不重复 的全排列。
难度
中等
示例
示例 1：
输入：nums = [1,1,2]
[[1,1,2], [1,2,1], [2,1,1]]
示例 2：
输入：nums = [1,2,3]
分析
这题是 046.全排列 的延续，但是纵向对比一下，就能发现这题和 046.全排列 的关系，其实和 039.组合总和 与 040.组合总和II 两者的关系如出一辙。
如果说nums中没有重复元素的话，那么这道题就跟 046.全排列 一模一样，可惜有重复元素的存在，让我们不得不重新考虑。
首先，因为nums内部的顺序并不会影响答案的组成，所以我们不妨把它们从小到大排个序，让他们相同的归属到一起，方便我我们参考 040.组合总和II 的方法来处理重复的元素。
还是按照 046.全排列 的思路来挨个选择合适的排列，然后加入答案中。
来看这个例子：nums = [1,1,2] 如果按照 046.全排列 的思路的话，我们会得到这样子的结果：
ans = [
[1,2,1],[1,1,2],[1,2,1],[2,1,1],[2,1,1]]
因为这个思路会把两个一样的1强硬的加上序号，让它们有了 差别 ，但实际上它们并无差别，所以怎么来避开呢？
其实我们只要保证同个位置同个元素只被填入一次即可。
给出以下的一个判断条件：
if(vis[i] || (i > 0 && numsIn[i] == numsIn[i - 1] && !vis[i - 1]))
如果符合上述条件，直接跳过当前元素的枚举即可。
下面给出一个粗略证明上述条件的合法性：
首先如果当前nums[i]已经使用过了——也就是vis[i] == true的话，那么显然是不能够再次选择的。
如果当前元素与前一个元素重复了，而且前面一个元素还没有被使用的时候，我们不能使用当前元素，这样子其实是规定了每个重复元素的排列，让每个重复的元素只能按照唯一固定的顺序来加入list中，从而防止了本来是一样的元素，结果两个仅仅是调换顺序，则形成了新的排列（实际上并没有）。
class Solution {
boolean[] vis; int[] numsIn;
private void DFS(List
时间复杂度：
时间复杂度其实和 046.全排列 是一样的，因为我们只是多了一个排序和一个规定重复元素顺序的操作，所以大体上并无差别。
总结
我们在做题的时候不仅仅要纵向对比（ 046.全排列 和 047.全排列 II），也要横向对比 （ 040.组合总和 II 和 047.全排列 II），这样子才能够充分从过去的题解中汲取力量，从而更加容易的解决眼下的题目。
力扣链接：https://leetcode.cn/problems/permutations-ii/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。
一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 890 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！
047.全排列 II
题意
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有 不重复 的全排列。
难度
中等
示例
示例 1：
输入：nums = [1,1,2]
[[1,1,2], [1,2,1], [2,1,1]]
示例 2：
输入：nums = [1,2,3]
分析
这题是 046.全排列 的延续，但是纵向对比一下，就能发现这题和 046.全排列 的关系，其实和 039.组合总和 与 040.组合总和II 两者的关系如出一辙。
如果说nums中没有重复元素的话，那么这道题就跟 046.全排列 一模一样，可惜有重复元素的存在，让我们不得不重新考虑。
首先，因为nums内部的顺序并不会影响答案的组成，所以我们不妨把它们从小到大排个序，让他们相同的归属到一起，方便我我们参考 040.组合总和II 的方法来处理重复的元素。
还是按照 046.全排列 的思路来挨个选择合适的排列，然后加入答案中。
来看这个例子：nums = [1,1,2] 如果按照 046.全排列 的思路的话，我们会得到这样子的结果：
ans = [
[1,2,1],[1,1,2],[1,2,1],[2,1,1],[2,1,1]]
因为这个思路会把两个一样的1强硬的加上序号，让它们有了 差别 ，但实际上它们并无差别，所以怎么来避开呢？
其实我们只要保证同个位置同个元素只被填入一次即可。
给出以下的一个判断条件：
if(vis[i] || (i > 0 && numsIn[i] == numsIn[i - 1] && !vis[i - 1]))
如果符合上述条件，直接跳过当前元素的枚举即可。
下面给出一个粗略证明上述条件的合法性：
首先如果当前nums[i]已经使用过了——也就是vis[i] == true的话，那么显然是不能够再次选择的。
如果当前元素与前一个元素重复了，而且前面一个元素还没有被使用的时候，我们不能使用当前元素，这样子其实是规定了每个重复元素的排列，让每个重复的元素只能按照唯一固定的顺序来加入list中，从而防止了本来是一样的元素，结果两个仅仅是调换顺序，则形成了新的排列（实际上并没有）。
class Solution {
boolean[] vis; int[] numsIn;
private void DFS(List
时间复杂度：
时间复杂度其实和 046.全排列 是一样的，因为我们只是多了一个排序和一个规定重复元素顺序的操作，所以大体上并无差别。
总结
我们在做题的时候不仅仅要纵向对比（ 046.全排列 和 047.全排列 II），也要横向对比 （ 040.组合总和 II 和 047.全排列 II），这样子才能够充分从过去的题解中汲取力量，从而更加容易的解决眼下的题目。
力扣链接：https://leetcode.cn/problems/permutations-ii/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。
一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 890 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！
047.全排列 II
题意
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有 不重复 的全排列。
难度
中等
示例
示例 1：
输入：nums = [1,1,2]
[[1,1,2], [1,2,1], [2,1,1]]
示例 2：
输入：nums = [1,2,3]
分析
这题是 046.全排列 的延续，但是纵向对比一下，就能发现这题和 046.全排列 的关系，其实和 039.组合总和 与 040.组合总和II 两者的关系如出一辙。
如果说nums中没有重复元素的话，那么这道题就跟 046.全排列 一模一样，可惜有重复元素的存在，让我们不得不重新考虑。
首先，因为nums内部的顺序并不会影响答案的组成，所以我们不妨把它们从小到大排个序，让他们相同的归属到一起，方便我我们参考 040.组合总和II 的方法来处理重复的元素。
还是按照 046.全排列 的思路来挨个选择合适的排列，然后加入答案中。
来看这个例子：nums = [1,1,2] 如果按照 046.全排列 的思路的话，我们会得到这样子的结果：
ans = [
[1,2,1],[1,1,2],[1,2,1],[2,1,1],[2,1,1]]
因为这个思路会把两个一样的1强硬的加上序号，让它们有了 差别 ，但实际上它们并无差别，所以怎么来避开呢？
其实我们只要保证同个位置同个元素只被填入一次即可。
给出以下的一个判断条件：
if(vis[i] || (i > 0 && numsIn[i] == numsIn[i - 1] && !vis[i - 1]))
如果符合上述条件，直接跳过当前元素的枚举即可。
下面给出一个粗略证明上述条件的合法性：
首先如果当前nums[i]已经使用过了——也就是vis[i] == true的话，那么显然是不能够再次选择的。
如果当前元素与前一个元素重复了，而且前面一个元素还没有被使用的时候，我们不能使用当前元素，这样子其实是规定了每个重复元素的排列，让每个重复的元素只能按照唯一固定的顺序来加入list中，从而防止了本来是一样的元素，结果两个仅仅是调换顺序，则形成了新的排列（实际上并没有）。
class Solution {
boolean[] vis; int[] numsIn;
private void DFS(List
时间复杂度：
时间复杂度其实和 046.全排列 是一样的，因为我们只是多了一个排序和一个规定重复元素顺序的操作，所以大体上并无差别。
总结
我们在做题的时候不仅仅要纵向对比（ 046.全排列 和 047.全排列 II），也要横向对比 （ 040.组合总和 II 和 047.全排列 II），这样子才能够充分从过去的题解中汲取力量，从而更加容易的解决眼下的题目。
力扣链接：https://leetcode.cn/problems/permutations-ii/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。
一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 890 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！
知识星球
扫码加入星球
查看更多优质内容
https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412