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

public class Solution {
    boolean[] marked;
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        //存储总的返回结果
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        //存合法全排列
        LinkedList<Integer>  track = new LinkedList<>();
        
        marked = new boolean[num.length];
        //排序
        Arrays.sort(num);
        backtrack(num, result,track);
        return result;
    }
    
    public void backtrack(int[] num, ArrayList<ArrayList<Integer>> result, LinkedList<Integer> track){
        if(track.size() == num.length){
            //一个全排列
            result.add(new ArrayList<Integer>(track));
            return;
        }
        for(int i = 0;i< num.length;i++){
              if(marked[i] || i >0 && num[i] == num[i-1] &&!marked[i-1]){
                  // i 访问过了 
                  //或者 回溯后 i本次回溯完变成了fasle  下一次 i+1的时候 如果数相等 那就不需要再遍历了 针对i而言 就是i-1
                   continue;
                }
             track.add(num[i]);
            //已经访问过了
            marked[i] = true;
            //寻找下一个 数据
            backtrack(num, result, track);
            //回溯 最后一个数删除
            track.removeLast();
            //每一次排列 都需要重置再来
            marked[i] = false;
        }

    }
}