题解 | 有重复项数字的全排列

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型一维数组 
     * @return int整型ArrayList<ArrayList<>>
     */
    // 有重复数字的全排列，可以认为是在没有重复的基础上增加一些判断操作，如果res里面已经有了就不用再加入了。
    // 这样写是错误的，因为在递归的时候，之前的条件是不包括，就加入list 现在不能这样了。因此在递归的时候要增加一个visited 数组
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    public void backTrace(int [] num,ArrayList<Integer> list,boolean[]visited){
        ArrayList<Integer> newList = new ArrayList<>(list);
        if(num.length==newList.size()){
            if(!res.contains(newList)){
                res.add(newList);

            }
        }
        int len = newList.size();
        for(int k = 0;k<num.length;k++){
            if(!visited[k]){
                newList.add(num[k]);
                visited[k] = true;
                backTrace(num,newList,visited);
                newList.remove(newList.size()-1);
                visited[k] = false;
            }
                

        }
    }
    public ArrayList<ArrayList<Integer>> permuteUnique (int[] num) {
        // 题目要求最后的结果是要求字典升序排列，本来的想法是对最后的结果执行一个操作，但是突然想到如果原始数组是升序排列，那么最后的结果是否也就是升序排列的。因此先调用Array.sort(num)进行升序排列，注意这个方法直接对原始数组进行操作，是不需要接受返回值的
        Arrays.sort(num);
        // write code here
        ArrayList <Integer> list = new ArrayList <Integer>();
        //默认是false
        boolean[]visited = new boolean[num.length];
        backTrace(num,list,visited);
        return res;
        
    }

}