import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        //定义一个TreeSet,指定排序规则(字典序规则)
        TreeSet<ArrayList<Integer>> set = new TreeSet<>(new Comparator<ArrayList<Integer>>() {
            public int compare(ArrayList<Integer> arr1 , ArrayList<Integer> arr2) {
                for(int i = 0 ; i < arr1.size() ; i ++) {
                    if(arr1.get(i) > arr2.get(i)) {
                        return 1 ;
                    } else if (arr1.get(i) < arr2.get(i)) {
                        return -1 ;
                    }
                }
                return 0 ;
            }
        }) ;
        help(num , 0 , new ArrayList<>() , set) ;
        ArrayList<ArrayList<Integer>> res = new ArrayList<>(set) ;
        return res ;
    }
    /*
    得到arr[start]及其之后所有元素的全排列,并将结果保存到res中
    其中tmp保存的是当前arr[start]的值
    */
    public void  help(int []arr , int start , ArrayList<Integer> tmp,TreeSet<ArrayList<Integer>> res) {
        if(start == arr.length) {
            ArrayList<Integer> r = new ArrayList<>(tmp) ;
            res.add(r) ;
            return ;
        }
        for(int j = start ; j < arr.length ; j ++) {//这个位置之后的元素,都可能出现在这个位置
            swap(arr , start , j) ;//和j位置元素交换
            tmp.add(arr[start]) ;//保存新的arr[start]
            help(arr , start + 1 , tmp , res) ;//求这个start之后的元素的全排列
            swap(arr , start , j) ;//递归返回后恢复现场
            tmp.remove(tmp.size()-1) ;//移除当前元素,恢复现场
        }            
        
    }
    //交换元素
    public void swap(int num[] , int i , int j) {
        int t = num[i] ;
        num[i] = num[j] ;
        num[j] = t ;
    }
}