给定一个可包含重复数字的序列 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]]
提示:
- 1 <= nums.length <= 8
- -10 <= nums[i] <= 10
思路
这道题目和排列问题的区别在与给定一个可包含重复数字的序列,要返回所有不重复的全排列。
这里又涉及到去重了。
在求组合总和(三) ,求子集问题(二)我们分别详细讲解了组合问题和子集问题如何去重。
那么排列问题其实也是一样的套路。
还要强调的是去重一定要对元素经行排序,这样我们才方便通过相邻的节点来判断是否重复使用了。
我以示例中的 [1,1,2]为例 (为了方便举例,已经排序)抽象为一棵树,去重过程如图:
图中我们对同一树层,前一位(也就是nums[i-1])如果使用过,那么就进行去重。
一般来说:组合问题和排列问题是在树形结构的叶子节点上收集结果,而子集问题就是取树上所有节点的结果。
class Solution { List<List<Integer>> res=new ArrayList<>(); List<Integer> path=new ArrayList<>(); boolean[] used; public List<List<Integer>> permuteUnique(int[] nums) { used=new boolean[nums.length]; Arrays.sort(nums); process(nums); return res; } private void process(int[] nums){ if(path.size()==nums.length){ res.add(new ArrayList<>(path)); } for(int i=0;i<nums.length;i++){ // used[i - 1] == true,说明同⼀树⽀nums[i - 1]使⽤过 // used[i - 1] == false,说明同⼀树层nums[i - 1]使⽤过 // 如果同⼀树层nums[i - 1]使⽤过则直接跳过 if(i>0&&nums[i-1]==nums[i]&&!used[i-1]){ continue; } if(!used[i]){ //如果同⼀树⽀nums[i]没使⽤过开始处理 used[i]=true;//标记同⼀树⽀nums[i]使⽤过,防止同一树支重复使用 path.add(nums[i]); process(nums); //回溯,说明同⼀树层nums[i]使⽤过,防止下一树层重复 path.remove(path.size()-1); used[i]=false; } } } }
另一种解法
class Solution { public List<List<Integer>> permuteUnique(int[] nums) { List<List<Integer>> ans=new ArrayList<>(); List<Integer> numList=new ArrayList<>(); for(int i=0;i<nums.length;i++){ numList.add(nums[i]); } List<Integer> path=new ArrayList<>(); process(numList,path,ans); return ans; } private void process(List<Integer> numList,List<Integer> path,List<List<Integer>> ans){ //base case if(numList.isEmpty()){ ans.add(path); return; } HashSet<Integer> set=new HashSet<>(); for(int i=0;i<numList.size();i++){ if(!set.contains(numList.get(i))){ set.add(numList.get(i)); List<Integer> pickList=new ArrayList<>(path); pickList.add(numList.get(i)); List<Integer> nextList=new ArrayList<>(numList); nextList.remove(i); process(nextList,pickList,ans); } } } }