题目大意：
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ]
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=47
解题思路分析：
本题的本质实际上是将数组中的每一个元素都看作是一个节点，然后以每个节点作为起点dfs递归所有路径。不过本题与前一题相比，存在重复数字，这会导致不同的dfs路径存在相同的结果，比如数组[1,1,1]，虽然存在多条dfs路径，但是结果都是相同的。因此，解题时，我们需要先将数组排序，然后在dfs选择节点时，当前所有没有选择过的节点都是我们可以选择的路径（分叉），但是为了避免重复，这些节点中数值相同的节点只能选择一次。
如果你并不熟悉dfs深度优先搜索算法，建议你先参考一下我之前讲过的文章：
LEETCODE常见算法之深度优先搜索DFS超详细白话讲解(上)
实现代码：
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
dfs(nums, new ArrayList<>(),new boolean[nums.length]);
return res;
}
void dfs(int[] nums, List<Integer> list, boolean[] visited){
if(list.size()==nums.length){
res.add(new ArrayList<>(list));
return;
}
for(int i=0;i<nums.length;i++){
if(visited[i]) continue;
if(i>0&&nums[i]==nums[i-1]&&!visited[i-1]) continue;
visited[i]=true;
list.add(nums[i]);
dfs(nums,list,visited);
visited[i]=false;
list.remove(list.size()-1);
}
}本题解法执行时间为1ms。
Runtime: 1 ms, faster than 99.41% of Java online submissions for Permutations II.
Memory Usage: 40.5 MB, less than 34.33% of Java online submissions for Permutations II.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-47-permutations-ii-解题思路分析/