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

import java.util.*;

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++){
            //1.marked[i] 当前位置访问过
            //2.回溯的时候，相同的数字有没有用过，如何判断
            // 从n-1位回溯到n-2，此时marked[n-2]和marked[n-1] 会变成false,然后i = n-1继续遍历,此时marked[n-2]是false
            //试想一下，从第0位开始，递归的时候，会出现num[i] == num[i-1]并且marked[i-1] = false吗？不会
            if( (i > 0 && num[i] == num[i-1] && !marked[i-1]) || marked[i]){
                continue;
            }
            track.add(num[i]);
            //已经访问过了
            marked[i] = true;
            //寻找下一个 数据
            backtrack(num, result, track);
            //回溯 最后一个数删除
            track.removeLast();
            //每一次排列 都需要重置再来
            marked[i] = false;
        }

    }
}