有重复项数字的全排列

import java.util.*;

public class Solution {

    ArrayList<ArrayList<Integer>> list = new ArrayList<>(); // 存最终全排列结果
    ArrayList<Integer> tmp = new ArrayList<>(); // 当前排列结果
    Set<Integer> set = new HashSet<>(); // 存已用数组元素的下标，防重复

    public ArrayList<ArrayList<Integer>> permuteUnique (int[] num) {
        // write code here
        Arrays.sort(num); // 升序
        dfs(num);  // 调用 dfs
        return list;
    }
    
    // dfs
    public void dfs(int[] nums) {
        if (tmp.size() == nums.length) {
            ArrayList<Integer> t = new ArrayList<>(tmp);
            if (!list.contains(t)) list.add(t); // 由于元素可能重复，导致排列可能重复，要判断一下
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (set.contains(i)) continue; // 下标重复
            tmp.add(nums[i]);
            set.add(i);
            dfs(nums); // 排列数组下个元素
            tmp.remove(tmp.size() - 1); // 回溯
            set.remove(i);
        }
    }
}

从NC27 所有子集合的题解学习了dfs基本模版，链接地址【https://blog.nowcoder.net/n/e65e2933bb154e3fad60414e48848e88】

用到这里的全排列 (下一题同样适用，不用set，不用判断排列重复)

public ArrayList<ArrayList<Integer>> permuteUnique (int[] num) {
        ArrayList<ArrayList<Integer>> llst = new ArrayList<>();
        ArrayList<Integer> data = new ArrayList<>(num.length);
        Arrays.sort(num);
        for(int i=0;i<num.length;i++){
            data.add(i,num[i]);
        }
        permute(llst,new ArrayList<Integer>(),data);
        return llst;
    }

    public void permute(ArrayList<ArrayList<Integer>> llst,ArrayList<Integer> lst,ArrayList<Integer> data){
        if(data.size() == 0) llst.add(lst);
        HashSet<Integer> set =new HashSet<>();
        for(int i=0;i<data.size();i++){
            if(set.contains(data.get(i)))
                continue;
            set.add(data.get(i));
            ArrayList<Integer> t1 = new ArrayList<Integer>(lst);
            ArrayList<Integer> t2 = new ArrayList<Integer>(data);
            t1.add(t2.get(i));
            t2.remove(i);
            permute(llst,t1,t2);
        }
    }

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型一维数组
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> permuteUnique (int[] num) {
        // write code here
        // 左程云老师讲过全排列的分支限界递归法解决不重复全排列问题
        // 调用一个递归函数，这个递归函数负责对当前i位置的数字进行与i ~ num.length - 1中的位置依次互换，然后继续考察i + 1处的情况
        // 分支界限法去重：定义一个HashSet，这个位置没有出现过该值才允许进入分支，否则跳过

        // 算法的时间复杂度0(N!)，额外空间复杂度0(N!)

        // 用于记录所有路径的结果
        ArrayList<ArrayList<Integer>> finalResults = new ArrayList<>();

        // 调用这个递归函数，从num数组的0位置开始，将每一次找到的oneResult填进finalResult中
        process(num, finalResults, 0);

        // 给finalResults中的元素按照字典序升序排列
        finalResults.sort((o1, o2) -> {
            // 遍历两个list的每个元素，找到第一对不相同的，按照升序返回
            int i = 0, j = 0;
            while (i < o1.size() && j < o2.size()) {
                if (o1.get(i) != o2.get(j)) {
                    return o1.get(i) - o2.get(j);
                }
                i++;
                j++;
            }
            return 0;
        });

        // 返回最终的答案finalResults
        return finalResults;
    }

    public void process(int[] num, ArrayList<ArrayList<Integer>> finalResults, int i) {
        // 递归出口（底部）
        if (i == num.length) {
            // i越界了，说明整个数组遍历完毕了，将单个路径上的答案oneResult写入总答案finalResults中
            // 踩坑点1：这里一定要【现场新创建】一个ArrayList放入答案中，如果提前在主方法创建好，那么随着每次递归的调用，finalResults里面的值也会被修改
            ArrayList<Integer> oneResult = new ArrayList<>();
            for (Integer n : num) {
                oneResult.add(n);
            }
            finalResults.add(oneResult);
        }

        // 递归分支
        HashSet<Integer> set = new HashSet<>();
        for (int j = i; j < num.length; j++) {
            if (!set.contains(num[j])) {
                // 将num[j]登记
                set.add(num[j]);
                // 假设本位置与j位置的元素交换
                swap(num, i, j);
                // 在交换完的基础上继续考察num数组中i+1往后的位置该如何排列
                process(num, finalResults, i + 1);
                // 注意！恢复现场，继续尝试将本位值与num[j + 1]位置的元素交换
                // 踩坑点2：一定要【恢复现场】，要不然无法准确列出要分支的情况
                swap(num, j, i);
            }
        }
    }

    // 数组元素交换函数
    public void swap(int[] num, int i, int j) {
        if (i == j) {
            return;
        }
        int t = num[i];
        num[i] = num[j];
        num[j] = t;
    }
}

ArrayList<ArrayList<Integer>> res=new ArrayList<>();

public ArrayList<ArrayList<Integer>> permuteUnique (int[] num) {
    // write code here
    Arrays.sort(num);
    dfs(num ,new boolean[num.length] ,new ArrayList<>());
    return res;
}

public void dfs(int[] num ,boolean[] flag ,ArrayList<Integer> list){
    if(list.size()==num.length){
        res.add(new ArrayList<Integer>(list));
        return;
    }
    for(int i=0;i<num.length;i++){
        // 跳过重复数据&nbs***bsp;已加入数据
        if((i>0 && num[i]==num[i-1] && !flag[i-1]) || flag[i]){
            continue;
        }
        flag[i]=true;
        list.add(num[i]);
        dfs(num ,flag ,list);
        list.remove(list.size()-1);
        flag[i]=false;
    }
}

import java.util.*;


public class Solution {



    //声明几个全局的，懒得在迭代方法传值
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    ArrayList<Integer> arry = new ArrayList<>();
    //既然元素有重复的，那么我们就拿索引出来排序，索引肯定不重复
    ArrayList<Integer> index = new ArrayList<>();

    // 入口方法
    public ArrayList<ArrayList<Integer>> permuteUnique (int[] num) {
        //先按字典序排序
        Arrays.sort(num);
        permute(num);
        return res;
    }

    //迭代方法
    void permute(int[] num) {
        //2.迭代终止条件
        if (index.size() == num.length) {
            res.add(new ArrayList<>(arry));
            return;
        }
        //3.子部分执行方案
        ArrayList<Integer> temp = new ArrayList<>(); //每一层，已经选过的数据
        for (int i = 0; i < num.length; i++) {
            //相同位置，或者值相同都不应该 选取
            //（可以用map ， key存索引，值存数组的值，但是map最后输出成数组还得再迭代一下，所以这里索引和值还是分开处理吧）
            if (index.contains(i) || temp.contains(num[i])) continue;
            temp.add(num[i]);
            index.add(i);
            arry.add(num[i]);
            //1.递归模型
            permute(num);
            //4. 回溯
            index.remove(index.size() - 1);
            arry.remove(arry.size() - 1);
        }

    }



}

public ArrayList<ArrayList<Integer>> permuteUnique (int[] num) {
        ArrayList<ArrayList<Integer>> ans=new ArrayList<>();
        //要先排序，从才能让相邻的元素挨着
        Arrays.sort(num);
        ArrayList<Integer> list=new ArrayList<>();
        boolean[] used=new boolean[num.length];
        build(num,ans,list,used);
        return ans; 
    }
    public void build(int[] num,ArrayList<ArrayList<Integer>> ans,ArrayList<Integer> list,boolean[] used){
        if(list.size()==num.length){
            ans.add(new ArrayList<>(list));
        }
        for(int i=0;i<num.length;i++){
            if(used[i]==true) continue;
            if(i>0&&num[i]==num[i-1]&&used[i-1]==true) continue;
            list.add(num[i]);
            used[i]=true;
            build(num,ans,list,used);
            list.remove(list.size()-1);
            used[i]=false;
        }
    }

import java.util.*;
//正常排再去重
public class Solution {
    ArrayList<ArrayList<Integer>> al = new ArrayList<>();
    boolean[] dp;
    public void back(int[] num, boolean[] dp, ArrayList<Integer> list) {
        if (list.size() == num.length) {
            al.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < num.length; i++) {
            if (dp[i]) continue;
            dp[i] = true;
            list.add(num[i]);
            back(num, dp, list);
            list.remove(list.size() - 1);
            dp[i] = false;
        }
    }
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        Arrays.sort(num);
        dp = new boolean[num.length];
        ArrayList<Integer> list = new ArrayList<>();
        Arrays.fill(dp, false);
        back(num, dp, list);
        HashMap<ArrayList<Integer>, Integer> hs = new HashMap<>();
        ArrayList<ArrayList<Integer>> al1 = new ArrayList<>();
        for (int i = 0; i < al.size(); i++) {
            ArrayList<Integer> a = al.get(i);
            if (!hs.containsKey(a)) {
                hs.put(a, 1);
                al1.add(a);
            }
        }
        return al1;
    }
}

递归

import java.util.*;

public class Solution {

    static ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    static boolean []mark;
    public static ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {

        Arrays.sort(num);
        mark = new boolean[num.length];
        LinkedList<Integer> list = new LinkedList<>();
        permute(num, list);
        return res;

    }

    private static void permute(int[] num, LinkedList<Integer> list) {
        // 递归的终结条件
        if (num.length == list.size()) {
            if (!res.contains(list)) {
                res.add(new ArrayList<>(list));
            }
            return;
        }

        for (int i = 0; i < num.length; i++) {
            if (mark[i]) {
                continue;
            }
            list.add(num[i]);
            mark[i] = true;
            permute(num, list);

            list.removeLast();
            mark[i] = false;
        }
    }
}

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        Arrays.sort(num);
        ArrayList<ArrayList<Integer>> list=new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> path=new ArrayList<Integer>();
        dfs(num,path,list);
        ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();//去重后再装入list
        for(int i=0;i<=list.size()-1;i++){//将list去重
            if(res.contains(list.get(i))){continue;}
            res.add(list.get(i));
        }
        return res;
    }
    
    public void dfs(int[] arr,ArrayList<Integer> path,ArrayList<ArrayList<Integer>> list){
        if(path.size()==arr.length){
            ArrayList<Integer> sublist=new ArrayList<Integer>();
            for(int i=0;i<=path.size()-1;i++){
                sublist.add(arr[path.get(i)]);
            }
            list.add(new ArrayList<Integer>(sublist));
            return;
        }
        for(int i=0;i<=arr.length-1;i++){
            if(path.contains(i)){continue;}
            path.add(i);
            dfs(arr,path,list);
            path.remove(path.size()-1);
        } 
    }

}