[数据结构与算法]NC42有重复项数字的全排列

描述

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

题解：也就是判断是否略过下一个数组元素。当下一个元素和上一个元素相同且上一个元素已被访问回溯，则掠过。关键bug在于不要使用ArrayList<Integer>，这种情况下，会返回未知的错误，应该要使用LinkedList<Integer>。具体原因，我也还没有搞清楚，来日方长吧。

public class Solution {
    boolean mark[];
    ArrayList<ArrayList<Integer>> list=new ArrayList<>();
    LinkedList<Integer> temp=new LinkedList();
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        mark=new boolean [num.length];
        Arrays.sort(num);
        all_sort(num);
        return list;
    }
    public void all_sort(int[] num){
        if(temp.size()==num.length)
        {
            list.add(new ArrayList<Integer>(temp));
            return;
        }
         
        for(int i=0;i<num.length;i++)
        {
             if(mark[i] || i>0&&num[i]==num[i-1]&&!mark[i-1])
             {
                 continue;
             }
            temp.add(num[i]);
            mark[i]= true;
            all_sort(num);
            temp.removeLast();
            mark[i]=false;
        }
    }
}