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

描述

给出一组可能包含重复项的数字，返回该组数字的所有排列。结果以字典序升序排列。

数据范围： 0<n≤80<n≤8 ，数组中的值满足 −1≤val≤5−1≤val≤5

要求：空间复杂度 O(n!)O(n!)，时间复杂度 O(n!)O(n!)

示例1

输入：

[1,1,2]

返回值：

[[1,1,2],[1,2,1],[2,1,1]]

示例2

输入：

[0,1]

返回值：

[[0,1],[1,0]]

此题同 【回溯-全排列&&dfs】leet-47. 全排列一样，不同之处在于上一题没有要求结果输出字典顺序。所以本题必须要先排序。

方法一：

public ArrayList<ArrayList<Integer>> permuteUnique (int[] nums) {
        // write code here
       Arrays.sort(nums);
        int n=nums.length;
        boolean[] f=new boolean[n];
        ArrayList<ArrayList<Integer>> ans=new ArrayList<>();
        dfs(nums,new ArrayList<>(),f,ans);
        return ans;
    }
 
    public void dfs(int[] nums,List<Integer> path,boolean[] u,ArrayList<ArrayList<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++;
        }
    }

方法二：

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

    public void dfs(int[] nums, List<Integer> path, boolean[] u,
                    ArrayList<ArrayList<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】蜜蜂采蜜