有重复项数字的全排列

因为交换位置可能会出现重复交换的情况，出现的结果需要去重，因此不便于使用交换位置的方法。

step 1：我们就使用临时变量去组装一个排列的情况：每当我们选取一个数组元素以后，就确定了其位置，相当于对数组中剩下的元素进行全排列添加在该元素后面，给剩余部分进行全排列就是一个子问题，因此可以使用递归。

终止条件：临时数组中选取了n个元素，已经形成了一种排列情况了，可以将其加入输出数组中。 返回值：每一层给上一层返回的就是本层级在临时数组中添加的元素，递归到末尾的时候就能添加全部元素。 本级任务：每一级都需要选择一个元素加入到临时数组末尾（遍历数组选择）。首先已经加入的元素不能再次加入了，因此我们需要使用额外的vis数组用于记录哪些位置的数字被加入了。同时为了去除重复元素的影响，如果当前的元素num[i]与同一层的前一个元素num[i-1]相同且num[i-1]已经用过了，也不需要将其纳入。

step 2：回溯的思想也与没有重复项数字的全排列类似，对于数组[1,2,2,3]，如果事先在临时数组中加入了1，后续子问题只能是[2,2,3]的全排列接在1后面，对于2开头的分支达不到，因此也需要回溯：将临时数组刚刚加入的数字pop掉，同时vis修改为没有加入，这样才能正常进入别的分支。

 public void recure(ArrayList<ArrayList<Integer>> lists,ArrayList<Integer> list,boolean[] vis,int[] num){

        if(list.size()== num.length) lists.add(new ArrayList<>(list));

        for (int i=0;i<num.length;i++){

            if(vis[i]) continue;
            if(i>0&&num[i]==num[i-1]&&!vis[i]) continue;

            vis[i]=true;
            list.add(num[i]);
            recure(lists,list,vis,num);
            vis[i]=false;
            list.remove(list.size()-1);


        }

    }

    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        Arrays.sort(num);
        boolean[] vis=new boolean[num.length];
        ArrayList<ArrayList<Integer>> lists=new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> list=new ArrayList<Integer>();
        Arrays.fill(vis,false);
        recure(lists,list,vis,num);
        return lists;

    }