哪吒教你玩转全排列：递归的奇妙冒险

大家好，我是哪吒！今天咱们不闹海，也不打妖怪，来点技术活儿——全排列！没错，就是那个让你头秃的递归问题。不过别怕，有我在，保证让你笑着学会！

一、全排列是啥？

全排列，简单来说就是把一组数字重新排列，看看有多少种不同的组合。比如 [1, 2, 3] 的全排列就是：

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

看起来简单吧？但如果你用暴力枚举，数字一多，你的电脑可能就要罢工了。所以，咱们得用点高级的招数——递归！

二、递归是啥？哪吒来给你打个比方

想象一下，哪吒有三头六臂（虽然我只有三头，但六臂听起来更酷）。每只手臂都可以选择拿一个数字，但每只手臂只能拿一个，而且不能重复。

1. 第一只手臂：可以选择 1、2 或 3。
2. 第二只手臂：从剩下的数字里选一个。
3. 第三只手臂：只能拿最后一个数字。

这个过程就是递归的核心思想：每一步都做一个选择，然后交给下一步去处理，直到没有选择为止。

三、递归的实现思路

咱们用 Java 代码来实现这个逻辑。先看看代码：

public List<List> permute(int[] nums) {
    List<List> res = new ArrayList<>();
    Deque deque = new ArrayDeque<>();
    boolean[] condition = new boolean[nums.length];
    dfs(res, deque, condition, 0, nums, nums.length);
    return res;
}

public void dfs(List<List> res, Deque deque, boolean[] condition, int index, int[] nums, int length) {
    // 如果当前排列长度等于数组长度，说明已经完成一个排列
    if (deque.size() == length) {
        res.add(new ArrayList<>(deque));
        return;
    }
    // 遍历所有可能的数字
    for (int i = 0; i < length; i++) {
        // 如果数字已经被使用过，跳过
        if (condition[i]) {
            continue;
        }
        // 选择当前数字
        deque.add(nums[i]);
        condition[i] = true;
        // 递归处理下一步
        dfs(res, deque, condition, index, nums, length);
        // 回溯：撤销选择，尝试其他可能性
        condition[i] = false;
        deque.removeLast();
    }
}

代码解析

1. permute 方法：
2. 初始化结果列表 res 和双端队列 deque（用来存储当前排列）。
3. 创建一个布尔数组 condition，用来记录哪些数字已经被使用过。
4. 调用 dfs 方法开始递归。
5. dfs 方法：
6. 终止条件：如果当前排列的长度等于数组长度，说明已经完成一个排列，将其加入结果列表。
7. 遍历数字：尝试每一个数字。
8. 剪枝：如果数字已经被使用过，跳过。
9. 选择：将当前数字加入排列，并标记为已使用。
10. 递归：继续处理下一步。
11. 回溯：撤销选择，尝试其他可能性。

四、递归的精髓：回溯

递归的核心在于回溯。每次选择一个数字后，递归处理剩下的数字，处理完后撤销选择，再尝试其他可能性。这就像哪吒的六臂，每只手臂都可以尝试不同的选择，直到找到所有可能的排列。

五、C++ 实现

为了照顾 C++ 的小伙伴，我也准备了 C++ 版本的代码：

vector<vector> permute(vector& nums) {
    vector<vector> res;
    vector path;
    vector used(nums.size(), false);
    dfs(0, used, res, path, nums.size(), nums);
    return res;
}

void dfs(const int deepth, std::vector& used,
         vector<vector>& res, vector& path, const int length,
         vector& nums) {
    if (length == path.size()) {
        res.emplace_back(path);
        return;
    }
    for (int i = 0; i < length; i++) {
        if (used[i]) {
            continue;
        }
        path.emplace_back(nums[i]);
        used[i] = true;
        dfs(deepth + 1, used, res, path, length, nums);
        used[i] = false;
        path.pop_back();
    }
    return;
}

逻辑和 Java 版本完全一致，只是语法不同。C++ 的小伙伴可以直接拿去用！

六、递归的思考题

1. 如果数组中有重复数字怎么办？
2. 比如 [1, 1, 2]，如何避免生成重复的排列？
3. 提示：可以在递归时跳过重复的数字。
4. 递归的时间复杂度是多少？
5. 对于 n 个数字，全排列的数量是 n!，所以时间复杂度是 O(n!)。
6. 如何优化递归的性能？
7. 提示：可以尝试剪枝或动态规划。

七、哪吒的坚持

写代码就像修炼，递归就像哪吒的三头六臂，虽然一开始看起来很复杂，但只要你坚持练习，一定能掌握其中的奥妙！记住，每一次递归调用，都是对自己的一次挑战。坚持下去，你也能成为编程界的“哪吒”！

好了，今天的全排列教程就到这里。如果你觉得有用，记得点赞、转发、评论三连！下次再见，咱们继续闹海打妖怪！