PermutationsIIPermutations链接：https://leetcode-cn.com/problems/permutations-ii给定一个可以包含重复数字的序列nums，按任意顺序返回所有不重复的全排列。示例1：输入：nums=[1,1,2]输出：[[1,1,2],[1,2,1],[2,1,1]]示例2：输入：nums=[1,2,3]输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]Tips:1<=nums.length<=8-10<=nums[i]<=10思路如果不知道回溯算法的基础，我还特地录了个视频：取你学习回溯算法（理论）你可以结合解决方案和视频一起观看。希望对大家理解回溯算法有所帮助。本题与全排列的区别在于，给定一个可以包含重复数字的序列，需要返回所有不重复的全排列。这里又涉及到去重。在CombinationSumII和SubsetII中，我们分别详细讲解了如何去重组合问题和子集??问题。那么排列问题其实也是同样的套路。还需要强调的是，元素一定要经过排序去重，这样我们就可以很容易的判断出它们是否通过相邻的节点被重用了。我以例子中的[1,1,2]为例（为了例子方便，已经排序），抽象为一棵树。就是nums[i-1])如果已经被使用过，那么就会去重。一般来说：组合问题和排列问题在树结构的叶子节点上收集结果，而子集问题在树上的所有节点上收集结果。在46.FullArrangement中已经详细讲解了permutationproblem的写法，在40.CombinationsumII和90.SubsetII中详细讲解了deduplication的写法，所以这次不用回到三部曲分析，直接给出代码如下：{//此时，一个集合if(path.size()==nums.size()){result.push_back(path);return;}for(inti=0;i0&&nums[i]==nums[i-1]&&used[i-1]==false){continue;}if(used[i]==false){used[i]=true;path.push_back(nums[i]);backtracking(nums,used);path.pop_back();used[i]=false;}}}public:vector>permuteUnique(vector&nums){result.clear();path.clear();sort(nums.begin(),nums.end());//排序vectorused(nums.size(),false);backtracking(nums,used);returnresult;}};展开大家发现去重最关键的代码是：if(i>0&&nums[i]==nums[i-1]&&used[i-1]==false){continue;}如果改为used[i-1]==true，也对！，去重代码如下：if(i>0&&nums[i]==nums[i-1]&&used[i-1]==true){continue;}为什么会这样呢，上面我刚才说的，如果要对树层的前一位进行去重，使用used[i-1]==false，如果要对树层的前一位进行去重，使用used[i-1]==true对于排列问题，树层去重和树枝去重都是可以的，但是树层去重效率更高！是不是有点抽象？来吧，我就用输入：[1,1,1]来举例。树层去重的树结构（used[i-1]==false）如下：FullArrangementII2分支去重的树结构（used[i-1]==true）如下：全编排二大家应该很清楚，树层上的前位去重是非常彻底和高效的。对分支上的前一位进行去重虽然最终可以得到答案，但是做了很多无用的查找。总结一下，这道题其实是用了我们之前讲过的去重的思想，但是有意思的是，在去重的代码中，是这样写的：if(i>0&&nums[i]==nums[i-1]&&used[i-1]==false){continue;}并这样写：if(i>0&&nums[i]==nums[i-1]&&used[i-1]==true){continue;}都是可能的，这也是很多同学对这个话题感到困惑的地方。他们知道used[i-1]==false也可以，used[i-1]==true也可以，但他们就是不明白为什么。所以我以[1,1,1]为例，将这两种去重逻辑抽象成树状结构，大家一看就明白：为什么两种写法都可以，哪种写法效率更高！是不是一下子就清楚了？快乐！！本文转载自微信公众号“代码随想录”，可通过以下二维码关注。转载本文请联系CodeCaprice公众号。
