目录
题目概述(中等难度)
思路与代码
思路展现
代码示例
题目概述(中等难度)
题目链接：
点我进入leetcode
思路与代码
思路展现
这道题目就是经典的回溯+DFS(深度优先搜索遍历),在这里我就不再给出我关于回溯的讲解了，leetcode的大佬已经帮我们总结到位了，只需要跟着他的题解走即可,在这里宣传以下weiwei大佬是一位非常厉害的大佬，除了他自己写的题解意外，也开设了自己的github网站帮助大家学习算法，在这里我都会将其网站贴到下面：
全排列Ⅱweiwei大佬题解链接
weiwei大佬github链接
这道题目是全排列题目的再进一步延申，只不过这道题目加入了两个条件，第一个就是这个序列中的元素有重复的，第二个就是需要按照任意顺序返回不重复的，在之前的全排列题目中我们的序列没有重复元素，所以最终我们返回的全排列就是没有重复元素的，而这次我们序列是有重复元素的，那么最终我们返回的全排列就肯定有重复元素，所以此时就需要用到剪枝，什么是剪枝以及如何用大家直接看weiwei大佬的题解就行啦，链接我已经放到了上面.
其实这段代码针对于之前的全排列其实就只多了几行代码，如下所示：
第一处：
首先要对我们的数组进行排序，因为数组有序是剪枝的前提
Arrays.sort(nums);
第二处：
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) { continue; }
我们来解释下为什么要加上面的代码
1：首先一个比较容易想到的办法是在结果集中去重。但是问题来了，这些结果集的元素是一个又一个列表，对列表去重不像用哈希表对基本元素去重那样容易。
如果要比较两个列表是否一样，一个容易想到的办法是对列表分别排序，然后逐个比对。既然要排序，我们就可以 在搜索之前就对候选数组排序，一旦发现某个分支搜索下去可能搜索到重复的元素就停止搜索，这样结果集中不会包含重复列表，所以此时我们用到了剪枝.
2：
为什么要加上nums[i] == nums[i - 1]?
例如对于【1，1’，2】这个数组，如果我们加上这个条件的话，相当于1’这个会产生与之前1相同的全排列结果的数字就不会再进行判断，直接跳到2去
但此时同学们思考一个问题，光加上这个条件够吗？
答：当然不够，原因如下
假设只判断这两个是否相等，很容易将我们本来符合条件的全排列删掉，例如假设如果是【1，1，2】这种组合，最终输出的结果是不存在全排列，因为前后只要重复就全部被剪掉了，所以说我们最终需要加上额外的判断条件
放到我们OJ的测试用例里面我们会发现有如下测试用例不通过：
此时为什么会有上面的问题出现，这是因为我们在判断具有重复元素的时候，并没有判断这两个重复的这个元素到底是在同一路径还是同一层，如果是同一路径是不能被剪枝的，而在同一层是可以被剪枝的，而这时我们判断两个重复的元素是在同一条路径还是在同层路径的标准是nums[i - 1] == false来进行判断的，假如此时nums[i - 1] = false的话，就说明我们这两个重复元素是在同层：如下所示：此类情况是必须进行剪枝的：原因是我们之前的1已经被选择过，并且状态从true置为了false,而此时这个新的1跟刚才1情况相同，所以就不需要再走一遍了，直接进行剪枝就好
而当nums[i - 1] = true的话，此类情况如下：
这种情况就说明是不能剪枝的.
总结：
代码示例
class Solution { public List<List<Integer>> permuteUnique(int[] nums) { //len代表数组的长度 int len = nums.length; //path是一个双端队列，使用Deque的原因是官方题解所给出的 Deque<Integer> path = new LinkedList<>(); //设置我们的res List<List<Integer>> res = new ArrayList<>(); //设置我们所给定的nums数组中每个元素的初始状态为false boolean[] used = new boolean[len]; if(len == 0) { return res; } //排序是剪枝的前提 Arrays.sort(nums); dfs(path,used,nums,res,0,len); return res; } /* dfs方法参数介绍: path表示双端队列，用于存储我们所选择的路径上的数字 boolean数组用于表示数字的选择与被选择，被选择为true,没有为false res用于存储最后的返回结果 我们递归结束的条件与我们nums数组的长度len以及二叉树深度depth有很大的关系 */ public void dfs(Deque<Integer> path , boolean[] used , int[] nums , List<List<Integer>> res , int depth , int len) { if(depth == len) { //注意这里的写法其实是一个简便写法，就是直接实例化一个list集合然后将双端队列参数直接传入进去 res.add(new ArrayList<>(path)); //声明我们的递归终止条件 return; } //!used[i]就表示此时假设这个数字还没有被选中，它的反就一定为true,然后才能进入到下面的语句 for(int i = 0 ; i < len ; i++) { if(!used[i]) { // 剪枝条件：i > 0 是为了保证 nums[i - 1] 有意义 // 写 !used[i - 1] 是因为 nums[i - 1] 在深度优先遍历的过程中刚刚被撤销选择 if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) { continue; } //选中后将数字加入到path中 path.addLast(nums[i]); //选中后将状态置为true used[i] = true; //上面我们选择元素完毕后就开始我们的递归 dfs(path ,used , nums , res , depth + 1 , len); //进行完递归操作后接下来就需要我们进行撤回操作 //1:撤回操作的第一步是将状态置为false used[i] = false; //2:撤回操作的第二步是将数字从path中移除 path.removeLast(); } } } }
