哪吒的递归之旅：如何用代码生成所有子集

大家好，我是哪吒，今天我要带大家进入递归的奇妙世界。你们可能会问，哪吒不是忙着打妖怪吗？怎么还有空写代码？其实，打妖怪和写代码有很多相似之处，都需要耐心、坚持和一点点魔法（或者说逻辑）。今天，我们要解决的问题是：如何生成一个数组的所有子集。

1. 问题背景

假设你有一个数组 [1, 2, 3]，你需要生成它的所有子集。子集包括空集、单个元素、两个元素的组合，一直到整个数组本身。听起来很简单，对吧？但当你真正开始写代码时，你会发现这其实是一个递归的经典问题。

2. 递归的思路

递归就像哪吒的“三头六臂”，看似复杂，但其实每一步都在做同样的事情。我们来看看如何用递归来生成所有子集。

2.1 递归的基本思想

选择：对于数组中的每一个元素，我们有两个选择——要么把它加入当前子集，要么不加入。
递归：对于每一种选择，我们继续递归处理剩下的元素。
终止条件：当处理完所有元素时，我们就得到了一个完整的子集。

2.2 递归的详细步骤

让我们以数组 [1, 2, 3] 为例，详细说明递归的过程。

初始状态：当前子集为空 []，我们从第一个元素 1 开始。
选择1：将 1 加入子集，得到 [1]，然后递归处理剩下的元素 [2, 3]。
选择2：将 2 加入子集，得到 [1, 2]，然后递归处理剩下的元素 [3]。
选择3：将 3 加入子集，得到 [1, 2, 3]，然后递归处理剩下的元素 []。
终止条件：没有元素可处理，返回 [1, 2, 3]。
回溯：回到上一步，移除 3，得到 [1, 2]，然后继续处理其他选择。
重复上述过程，直到所有可能的子集都被生成。

3. 代码实现

3.1 Java版本

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

public void dfs(List<List> res, Deque deque, int index, int length, int[] nums) {
    res.add(new ArrayList<>(deque));  // 将当前子集加入结果集

    if (index == length) {
        return;  // 终止条件：处理完所有元素
    }

    for (int i = index; i < length; i++) {
        deque.add(nums[i]);  // 选择当前元素
        dfs(res, deque, i + 1, length, nums);  // 递归处理剩下的元素
        deque.removeLast();  // 回溯：移除当前元素
    }
}

3.2 C++版本

public:
    vector<vector> subsets(vector& nums) {
        vector<vector> res;
        vector deque;
        dfs(res, deque, 0, nums.size(), nums);
        return res;
    }

    void dfs(vector<vector>& res, vector& deque, int index,
             int length, vector& nums) {
        res.push_back(deque);  // 将当前子集加入结果集

        if (index == length) {
            return;  // 终止条件：处理完所有元素
        }

        for (int i = index; i < length; i++) {
            deque.push_back(nums[i]);  // 选择当前元素
            dfs(res, deque, i + 1, length, nums);  // 递归处理剩下的元素
            deque.pop_back();  // 回溯：移除当前元素
        }
    }

4. 代码解析

4.1 Java代码解析

subsets 方法：这是入口方法，初始化结果集 res 和双端队列 deque，然后调用 dfs 方法进行递归。
dfs 方法：这是递归的核心方法。每次递归调用时，都会将当前的子集 deque 加入结果集 res。然后通过循环和递归，依次选择或不选择当前元素，直到处理完所有元素。

4.2 C++代码解析

subsets 方法：与Java版本类似，初始化结果集 res 和向量 deque，然后调用 dfs 方法进行递归。
dfs 方法：递归的核心逻辑与Java版本一致，通过循环和递归生成所有子集。

5. 递归的思考

递归就像哪吒的“三头六臂”，看似复杂，但其实每一步都在做同样的事情。关键在于如何定义递归的终止条件和如何回溯。通过递归，我们可以优雅地解决许多复杂的问题。

6. 坚持的意义

写代码就像打妖怪，有时候你会遇到困难，但只要坚持下去，最终一定能找到解决问题的方法。递归也是如此，虽然一开始可能会觉得难以理解，但只要你不断练习，最终你会发现它的美妙之处。

7. 结语

希望通过这篇文章，你能对递归有更深入的理解，并且能够轻松地生成数组的所有子集。记住，无论是打妖怪还是写代码，坚持和耐心都是最重要的。下次再见，哪吒要继续去打妖怪了！

思考题：你能用递归的方法生成一个字符串的所有排列吗？试试看吧！

四时宝库

程序员的知识宝库

挑战刷leetcode第11天(回溯-子集-78)