目录

• 46. 全排列

46. 全排列

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

示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1]
输出：[[1]]

解：
1.对与DFS的题 画出下面这个图

2.设答案数组为ans ans中包含的一个个数组用arr标志
3.左边这个黑框第一列代表标志数组 用来记录这个数是否在arr中 第二列代表需要进行全排列的数组 本题解是[5,6,7] 本题是[1,2,3] 第三列代表当前遍历到哪一层 当层数=数组长度时 将arr加入ans中
4.由于本题数字不能重复使用 即不能出现[5,5,5] 这种数组 所以我们需要一个标志数组来记录 哪些数字加入了arr
5.DFS代码套路：
（1）先确定回溯条件：当层数=数组长度时 相当于遍历完了 完成了一次全排列 将arr加入ans中
（2）DFS代码：因为要全排列 所以第一步肯定是遍历数组 判断该数字是否已经在arr中 若不在 则加入 更改标志位 进入下一层 调用DFS
（3）执行完dfs(nums, flags, index, ans, arr);这行代码代表你已经完成一次全排列了 现在需要回溯：将刚才设置的标志位全部复原：从arr中弹出元素 复原标志位 改变层数
6.注意将arr添加到ans时 需要拷贝当前的arr添加到ans：arr.slice() 因为你后面还要对arr进行操作 比如回溯时会移除最后一个元素 那么ans中的arr也会跟着变 所以这里一定要记得拷贝！
代码如下：
JS：

var permute = function(nums) {
    let flags = [];
    for (let i = 0; i < nums.length; i++) {
        flags.push(false);
    }
    let ans = [];
    let arr = [];
    dfs(nums, flags, 0, ans, arr);
    return ans;
};
function dfs(nums, flags, index, ans, arr) {
    if (index === nums.length) {
        ans.push(arr.slice());
        return;
    }
    for (let i = 0; i < nums.length; i++) {
        if (!flags[i]) {
            arr.push(nums[i]);
            flags[i] = true;
            index++;
            dfs(nums, flags, index, ans, arr);
            arr.pop();
            flags[i] = false;
            index--;
        }
    }
}

也可以用set代替flags 代码如下：但是不建议这样做 因为在数据较少情况下 用数组比用set好

var permute = function(nums) {
        let flags = new Set();
        let ans = [];
    let arr = [];
    dfs(nums, flags, 0, ans, arr);
    return ans;
};
function dfs(nums, flags, index, ans, arr) {
    if (index === nums.length) {
        ans.push(arr.slice());
        return;
    }
    for (let i = 0; i < nums.length; i++) {
        if (!flags.has(i)) {
            arr.push(nums[i]);
            flags.add(i);
            index++;
            dfs(nums, flags, index, ans, arr);
            arr.pop();
            flags.delete(i);
            index--;
        }
    }
}

JAVA：

public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> lists = new LinkedList<>();
        List<Integer> list = new LinkedList<>();
        boolean[] used = new boolean[nums.length];
        dfs(nums,0,lists,list,used);
        return lists;
    }

    private static void dfs(int[] nums,int i,List<List<Integer>> lists,List<Integer> list,boolean[] used){
        if (i == nums.length) {
            lists.add(new LinkedList<>(list));
            return;
        }
        for (int j = 0; j < nums.length; j++) {
            int num = nums[j];
            if (!used[j]){
                used[j] = true;
                list.add(num);
                dfs(nums,i + 1,lists,list,used);
                used[j] = false;
                list.remove(list.size() - 1);
            }
        }
    }