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

import java.util.*;

public class Solution {
    private static final int N = 10;//排列的最大长度
    int[] path = new int[N];//存储深搜路径
    boolean[] isVisited = new boolean[N];//储存当前节点是否被访问过
    int[] realNum;//静态成员接收数组，以添加到列表中
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();//结果集合
    int step;//深搜的步数，也就是递归树的最大高度

    void dfs(int u) {
        //到达深搜底部记录结果
        if (u == step) {
            ArrayList<Integer> one = new ArrayList<>();//记录一个排列
            for (int i = 1; i <= step; i++) {
                one.add(realNum[path[i] - 1]);
            }
          //只需要比无重复数字全排列多判断一次
            if (!res.contains(one)) {
                res.add(one);
            }
        }
        for (int i = 1; i <= step; i++) {
            //如果当前节点未被访问过，则标记该节点，由该节点继续向下搜索
            if (!isVisited[i]) {
                path[u + 1] = i;
                isVisited[i] = true;
                dfs(u + 1);
                isVisited[i] = false;
            }
        }
    }

    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        realNum = num;
        Arrays.sort(realNum);//对数组进行排序
        step = realNum.length;//记录深搜步数
        dfs(0);
        return res;
    }
}