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

import java.util.*;

public class Solution {
    /**
     * 给出一组可能包含重复项的数字，返回该组数字的所有排列。结果以字典序升序排列。
     * */
    /*相对字典有序*/
    //用于标记是否访问过
    boolean []mark;
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        //存储总的返回结果集
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        //存储一个合法全排列
        LinkedList<Integer> track = new LinkedList<>();

        mark = new boolean[num.length];
        //因为存在重复项，为了更好的处理，将数组先排序
        Arrays.sort(num);

        Dfs(num, res, track);

        return res;
    }

    public void Dfs(int[] num, ArrayList<ArrayList<Integer>> res, LinkedList<Integer> track) {
        //若 找到一个全排列，则将它加进结果集中，然后返回(回溯)
        if (track.size() == num.length) {
            res.add(new ArrayList<Integer>(track));
            return;
        }
        for (int i = 0; i < num.length; i++) {
            // （1）当此时的被访问过，可跳过
            // （2）当i>0 &&此时的数等于它的上一个&&上一个没访问过(没访问过证明是回溯后将前面的置为false，所以此时避免重复得用 !mark[i-1] 满足要求然后跳过该数字)
            if (mark[i] || i > 0 && num[i] == num[i - 1] && !mark[i - 1]) {
                continue;
            }
            //添加进全排列数组中
            track.add(num[i]);
            //标记为已经访问
            mark[i] = true;
            //继续寻找下一个数
            Dfs(num, res, track);
            //将上一次全排列的结果中，最后一个数移除掉
            track.removeLast();
            //移除掉的数置为 未访问
            mark[i] = false;
        }
    }
}

解题思想：dfs套路，主要是重复元素跳过逻辑。