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

import java.util.*;
import java.util.LinkedList;
/**
 * 以下两道题目：
 * https://www.nowcoder.com/practice/a43a2b986ef34843ac4fdd9159b69863
 * https://www.nowcoder.com/practice/4bcf3081067a4d028f95acee3ddcd2b1
 */
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);

        backtrack(num,res,track);

        return res;
    }

    public void backtrack(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++){
            //mark[i] 这里很好理解，就是用过的数字不再重复使用；
            //首先注意num[] 一开始就已经排过序了
            // i>0 && num[i] == num[i-1] && !mark[i-1] 这个条件，相当于将num[]中相等的数字限制为一个整体。
            //例如数组 1,1,2   这个条件的意思是 只有 前面的1已经添加 后面的1才能加进去。
            // 如果将两个1分别称为 一 Ⅰ  那么 只允许出现  一 Ⅰ 而不会出现 Ⅰ一  这样一来 就不会有重复的全排列了。
            if(mark[i] || i>0 && num[i] == num[i-1] && !mark[i-1]){
                continue;
            }
            //添加进全排列数组中
            track.add(num[i]);
            //标记为已经访问
            mark[i] = true;
            //继续寻找下一个数
            backtrack(num,res,track);
            //将上一次全排列的结果中，最后一个数移除掉
            track.removeLast();
            //移除掉的数置为 未访问
            mark[i] = false;
        }
    }
}