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

import java.util.*;

public class Solution {
     private static final int N = 10;
    int step = 0;

    int[] path = new int[N];//保存深搜路径，也就是存储的下标值
    boolean[] isVisited = new boolean[N];//是否访问过的状态数组
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();//结果集
    int [] realNum;

    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]);
            }
            res.add(one);
            return;
        }
        //开始深搜
        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>> permute(int[] num) {
        realNum = num;
        Arrays.sort(realNum);
        step = realNum.length;//获取递归的层数
        dfs(0);//从第0层开始深搜
        return res;
    }
}