Leetcode-046-全排列

题目描述

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

方法：回溯算法（DFS）

• “回溯”指的是“状态重置”，可以理解为“回到过去”、“恢复现场”，是在编码的过程中，是为了节约空间而使用的一种技巧
• 同时回溯其实就是“深度优先遍历”特有的一种现象
• “全排列”就是一个非常经典的“回溯”算法的应用。我们知道，N 个数字的全排列一共有 N!这么多个。

以数组 [1, 2, 3] 的全排列为例。

我们先写以 1 开头的全排列，它们是：[1, 2, 3], [1, 3, 2]；
再写以 2 开头的全排列，它们是：[2, 1, 3], [2, 3, 1]；
最后写以 3 开头的全排列，它们是：[3, 1, 2], [3, 2, 1]。

• 我们只需要按顺序枚举每一位可能出现的情况，已经选择的数字在接下来要确定的数字中不能出现。按照这种策略选取就能够做到不重不漏，把可能的全排列都枚举出来。
  • 在枚举第一位的时候，有三种情况。
  • 在枚举第二位的时候，前面已经出现过的数字就不能再选择了。
  • 在枚举第三位的时候，前面两个出现过的数字已经不能再选择了。

我们先写以 1 开头的全排列，它们是：[1, 2, 3], [1, 3, 2]；
再写以 2 开头的全排列，它们是：[2, 1, 3], [2, 3, 1]；
最后写以 3 开头的全排列，它们是：[3, 1, 2], [3, 2, 1]。

使用编程的方法得到全排列，就是在这样的一个树形结构中进行编程，具体来说，就是执行一次深度优先遍历，从树的根结点到叶子结点形成的路径就是一个全排列。

1. 每一个节点表示了全排列问题求解不同的阶段，这些阶段通过变量的不同值体现。
2. 这些变量不同的值，也叫做状态
3. 使用深度优先遍历，可以借助系统的栈空间，为我们保存所需要的状态变量，具体做法是：
   • 往下走一层，将新的变量追加在尾部，
   • 而往回走的时候，需要撤销上一次的选择，也就是在尾部删除之前的操作
4. 这里我们需要用到两个变量数组
   • 已经选取了哪些数字，用path数组来记录
   • 一个布尔数组used,初始化的时候都为false,表示这些数字没有被选择，如果被选择值为true

废话不多说：show me the code(第一种：有错误的版本 )

（注意：这个代码是错误的，希望读者能自己运行一下测试用例自己发现原因，然后再阅读后面的内容）

import java.util.ArrayList;
import java.util.List;


public class Solution {

    public List<List<Integer>> permute(int[] nums) {
        // 首先是特判
        int len = nums.length;
        // 使用一个动态数组保存所有可能的全排列
        List<List<Integer>> res = new ArrayList<>();

        if (len == 0) {
            return res;
        }

        boolean[] used = new boolean[len];
        List<Integer> path = new ArrayList<>();

        dfs(nums, len, 0, path, used, res);
        return res;
    }

    private void dfs(int[] nums, int len, int depth,
                     List<Integer> path, boolean[] used,
                     List<List<Integer>> res) {
        if (depth == len) {
            res.add(path);
            return;
        }

        for (int i = 0; i < len; i++) {
            if (!used[i]) {
                path.add(nums[i]);
                used[i] = true;

                dfs(nums, len, depth + 1, path, used, res);
                // 注意：这里是状态重置，是从深层结点回到浅层结点的过程，代码在形式上和递归之前是对称的
                used[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        Solution solution = new Solution();
        List<List<Integer>> lists = solution.permute(nums);
        System.out.println(lists);
    }
}

这段代码在运行的时候输出如下：

[[], [], [], [], [], []]

错误的原因出现在这里：

if (depth == len) {
    res.add(path);
    return;
}

path 这个变量指向的变量在全局递归过程中只有一份存在，深度优先遍历完成之后，因为回到了根节点（撤销了之前的操作），因此path回到根节点以后就是空。

在java中，传递的对象的内存地址，这些地址实际上是同一块内存区域，所以说我们要做一次深拷贝

if (depth == len) {
    res.add(new ArrayList<>(path));
    return;
}

正确的版本

class Solution{
    public List<List<Integer>> permute(int[] nums){
        // 首先是特判
        int len = nums.length;
        // 使用一个动态数组来保存所有可能的全排列
        List<List<Integer>> res = new ArrayList<>();
        if(len == 0){
            return res;
        }

        // 一个布尔数组 used，初始化的时候都为 false 表示这些数还没有被选择，
        // 当我们选定一个数的时候，就将这个数组的相应位置设置为 true ，
        // 这样在考虑下一个位置的时候，就能够以 O(1） 的时间复杂度判断这个数是否被选择过，
        // 这是一种“以空间换时间”的思想。
        boolean[] used = new boolean[len];

        // path 这个变量所指向的对象在递归的过程中只有一份，
        // 深度优先遍历完成以后，因为回到了根结点（因为我们之前说了，从深层结点回到浅层结点的时候，需要撤销之前的选择），
        // 因此 path 这个变量回到根结点以后都为空。
        List<Integer> path = new ArrayList<>();

        dfs(nums,len,0,path,used,res);
        return res;
    }

    private void dfs(int[] nums, int len, int depth, List<Integer> path, boolean[] used, List<List<Integer>> res) {
        // depth 用来记录递归到了第几层
        // 用来结束递归，拿到当前的结果之后再撤销回上一层
        if (depth == len){
//            res.add(path);
            res.add(new ArrayList<>(path));
            return;
        }

        // else进行递归
        // 遍历所有nums中的数字
        for (int i = 0; i < len; i++) {
            // 是否这个数字之前已经用过
            if (!used[i]){
                path.add(nums[i]);
                used[i] = true;

                // 不断往下一层走
                dfs(nums, len, depth + 1, path, used, res);

                used[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }
}

复杂度分析：

• 时间复杂度：O(N * N!) N个节点，每个都要计算N！次
• 空间复杂度：O(N * N!) N个节点，每个都要存储N！次

打赏