【回溯-全排列&&dfs】leet-47. 全排列

给定一个可包含重复数字的序列 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

此题同：【回溯-全排列】leet-46. 全排列区别在于第46题没有重复数字，本题出现了重复数字，如果直接用46的方式会出现重复的排列。所以在dfs的选择过程中需要去重。

基于46题的方法一，在构建方案的第 i 位，需要从【i，n-1】上选择数字和第i位进行置换，在这个过程中 如果【i，n-1]区间有重复数字，此时swap之后选择第i 位就出现了重复选择。同一个数字在第i 位被选择了多次。

为避免重复选择，使用HashSet<Integer> 保存已经被选择过的数字，后面如果出现了重复，则直接跳过出现重复的数字的选择方案。

代码：

       public List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> paths=new ArrayList<>();
            dfs(nums,0,new ArrayList<>(),paths);
            return paths;
        }

        public void dfs(int[] nums,int i,List<Integer> path,List<List<Integer>> paths){
            if(i==nums.length){
                paths.add(new ArrayList<>(path));
                return;
            }
            HashSet<Integer> set=new HashSet<>();
            for(int k=i;k<nums.length;k++){
                if(set.contains(nums[k])) continue;
                set.add(nums[k]);
                
                swap(nums,i,k);
                path.add(nums[i]);
                dfs(nums,i+1,path,paths);
                path.remove(path.size()-1);
                swap(nums,i,k);
            }
        }

        public void swap(int[] nums,int i,int j){
            int t=nums[i];
            nums[i]=nums[j];
            nums[j]=t;
        }

基于46题的方法二, 则需要理解设置第i位的时候，相同的数字在这个位置只能设置1次，所以需要排序数组，

在用第k位设置 i 位置的数字的时候，如果它后面有与它相同的数字，这些数字的选择方案直接被过滤掉

代码：

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        int n=nums.length;
        boolean[] f=new boolean[n];
        List<List<Integer>> ans=new ArrayList<>();
        dfs(nums,new ArrayList<>(),f,ans);
        return ans;
    }

    public void dfs(int[] nums,List<Integer> path,boolean[] u,List<List<Integer>> ans){
        if(path.size()==nums.length){
             ans.add(new ArrayList<>(path));
             return;
        }

        for(int k=0;k<nums.length;){
            if(u[k]){
                k++;
                continue;
            } 
            
            u[k]=true;
            path.add(nums[k]);
            
            dfs(nums,path,u,ans);
            path.remove(path.size()-1);
            u[k]=false;

            int kval=nums[k];
            while(k<nums.length&&nums[k]==kval) k++;  //过滤重复
        }
    }

也可以不排序通过HashSet数组来过滤重复，所以以下也是可以：

    public List<List<Integer>> permuteUnique(int[] nums) {
        int n=nums.length;
        boolean[] f=new boolean[n];
        List<List<Integer>> ans=new ArrayList<>();
        dfs(nums,new ArrayList<>(),f,ans);
        return ans;
    }

    public void dfs(int[] nums,List<Integer> path,boolean[] u,List<List<Integer>> ans){
            if(path.size()==nums.length){
                ans.add(new ArrayList<>(path));
                return;
            }
            HashSet<Integer> set=new HashSet<>();
            for(int k=0;k<nums.length;k++){
                if(u[k] || set.contains(nums[k])){
                    continue;
                }
                set.add(nums[k]);
                
                u[k]=true;
                path.add(nums[k]);

                dfs(nums,path,u,ans);
                path.remove(path.size()-1);
                u[k]=false;

            }
    }

相似题目：

【回溯-全排列&&dfs】leet-46. 全排列

【回溯-全排列&&dfs】leet-47. 全排列

【回溯-全排列&&dfs】BM56 有重复项数字的全排列

【回溯-全排列&&dfs】OD100. 基站维修工程师

【回溯-全排列&&dfs】蜜蜂采蜜