力扣 47 全排列 深搜

题目链接

思路：比较标准的深搜，没什么好讲的。

代码

class Solution {
    public static int []A;
    public static int []vis;
    public static int N;
    public static int []source;

    public List<List<Integer>> list = new ArrayList<>();

    public void dfs(int index) {
        // 结束的条件
        if (index == N) {
            ArrayList<Integer> temp = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                temp.add(A[i]);
            }
            list.add(temp);
            return;
        }
        for (int i = 0; i < N; i++) {
            // 判断当前是否访问过
            if (vis[i] == 0) {
                // 优化减枝
                // 因为之前排序过，所以如果第一次和第二次选的是同一个数字的话，那么说明第二次重复了
                if (i > 0 && source[i] == source[i - 1] && vis[i - 1] == 1) {
                    continue;
                }
                vis[i] = 1;
                A[index] = source[i];
                dfs(index + 1);
                // 回溯
                vis[i] = 0;
            }
        }
    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        N = nums.length;
        A = new int[N];
        vis = new int[N];
        source = new int[N];
        source = nums;

        // 排序，去重的关键，在数组排完序，优化减枝之后，就已经去重了，想想为什么？
        Arrays.sort(source);

        dfs(0);
        return list;
    }
}