【回溯】学会全排列了吗？来看看子集问题！

利刃大大

发布于 2025-02-02 22:32:25

7200

代码可运行

文章被收录于专栏：csdn文章搬运csdn文章搬运

运行总次数：0

代码可运行

78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

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

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

解题思路

首先二话不说，先画决策树，这里一共有两种画法，它们在细节上是不同的，下图为画法一：

可以看到这种画法是根据每个元素选和不选的结果进行决策的，这种情况下，结果都是在叶子节点上的，也就是我们必须把决策树给遍历完才能找到最后的答案，这在一些题目中是会超时的，所以我们要换一种画法！

下图是画法二：

可以看到画法二的结果出现在了非叶子节点中，这就说明我们 可以对后面一些重复的结果进行剪枝，减少了无意义的操作，使得效率可以提高一些！下面我们就按画法二的思路来解决这道题！

函数头的设计：

因为返回值是一个二维数组，那其实可以和之前一样，用一个 全局的二维数组变量 ret 来记录结果集，最后返回 ret 即可，就不需要在函数头中作为参数传递！然后还可以再搞一个 全局变量 path 来存放路径上的元素集合，只不过需要注意的是因为设为全局变量，那么在回溯的时候需要对 path 进行回溯操作，防止影响后面的结果！

而对于函数头的话，因为我们需要知道当前层移动到了哪个元素，所以需要一个 index 变量来记录一下遍历起始位置！

vector<vector<int>> ret; // 结果集
vector<int> path;        // 存放路径上的元素集合

// 递归函数
void dfs(vector<int>& nums, int index);

函数体的内容：

因为这道题要求解集不能重复，那么就不像全排列问题那样每次都是从数组下标 0 开始遍历，而是从上一层传递进来的 index 下标开始遍历，我们依照从左往右的顺序去遍历元素，这样子就不会落下某个元素的情况，直到我们传入的 index 超出了原数组的范围就结束！
然后就是处理当前节点的问题，将当前节点的值也就是元素的值添加到 path 中，然后将 path 插入到结果集 ret 中即可！
接着就是递归函数去解决同一路径下去其它可能！
最后就是回溯处理，因为不能让当前层的下一层修改全局变量 path 之后，影响到当前层的后面其它集合的结果，所以我们需要将 path 中之前添加的元素进行弹出即可！

递归函数出口：

出口很简单，就是直到我们传入的 index 超出了原数组的范围就结束！

代码如下所示：

class Solution {
private:
    vector<vector<int>> ret; // 结果集
    vector<int> path;        // 存放路径上的元素集合
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        ret.push_back({}); // 先放个空集到结果集中
        dfs(nums, 0);
        return ret;
    }

    void dfs(vector<int>& nums, int index)
    {
        // 递归函数出口
        if(index >= nums.size())
            return;
        
        for(int i = index; i < nums.size(); ++i)
        {
            // 处理当前节点
            path.push_back(nums[i]);
            ret.push_back(path);

            // 递归处理其它路径，注意这里是i加一，而不是index加一
            dfs(nums, i + 1);

            // 进行回溯处理
            path.pop_back();
        }
    }
};

当然，我们也可以修改一下添加结果集的位置，这样子我们就不用先放个空集到结果集中，这个自行结合上面的画法理解一下，如下所示：

class Solution {
private:
    vector<vector<int>> ret; // 结果集
    vector<int> path;        // 存放路径上的元素集合
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return ret;
    }

    void dfs(vector<int>& nums, int index)
    {
        ret.push_back(path); // 先将当前path结果添加到结果集（起初path为空集）

        // 递归函数出口
        if(index >= nums.size())
            return;
        
        for(int i = index; i < nums.size(); ++i)
        {
            // 处理当前节点
            path.push_back(nums[i]);

            // 递归处理其它路径，注意这里是i加一，而不是index加一
            dfs(nums, i + 1);

            // 进行回溯处理
            path.pop_back();
        }
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-01-28，如有侵权请联系 cloudcommunity@tencent.com 删除

函数