【Leetcode 热题 100】46. 全排列

问题背景

给定一个不含重复数字的数组 $nums$，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

数据约束

• $1\le nums.length\le 6$
• $-10\le nums[i]\le 10$
• $nums$ 中的所有整数 互不相同

解题过程

回溯真的老大难，排列问题在递归的过程中是不知道之前元素是否被使用的，要用哈希表来判断是不是已经选择过，同时要注意恢复现场。
或者枚举当前位置可选的元素，用集合来判断，要注意避免并发修改异常。

具体实现

选或不选

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        int n = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        // 流程中答案是直接在对应位置上进行设置的，需要用这种方式定义有初始长度的列表
        List<Integer> path = Arrays.asList(new Integer[n]);
        boolean[] onPath = new boolean[n];
        dfs(0, nums, res, path, onPath);
        return res;
    }

    private void dfs(int i, int[] nums, List<List<Integer>> res, List<Integer> path, boolean[] onPath) {
        if(i == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        // i 枚举可能位置，j 访问可能元素
        for(int j = 0; j < nums.length; j++) {
            if(!onPath[j]) {
                path.set(i, nums[j]);
                onPath[j] = true;
                dfs(i + 1, nums, res, path, onPath);
                onPath[j] = false;
            }
        }
    }
}

选哪一个

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        Set<Integer> set = new HashSet<>();
        for(int num : nums) {
            set.add(num);
        }
        dfs(0, nums, res, path, set);
        return res;
    }

    private void dfs(int i, int[] nums, List<List<Integer>> res, List<Integer> path, Set<Integer> set) {
        if(i == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        // List 中有重载的 remove 方法，表达不同的删除语义，这里必须用包装类型来遍历
        for(Integer item : set) {
            path.add(item);
            Set<Integer> temp = new HashSet<>(set);
            temp.remove(item);
            dfs(i + 1, nums, res, path, temp);
            path.remove(item);
        }
    }
}