精选50题之 78. 子集

悠悠 2024-04-19 10:11 53阅读 0赞

### 腾讯精选练习（50 题）之 78. 子集 ###

*   *  原题目链接
     *  题目分析
     *  解题分析
     *  代码实现
     *  其他方式
     *  特殊方式
     *  写在最后

## [原题目链接][Link 1] ##

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。  
说明：解集不能包含重复的子集。

示例:

> 输入: nums = \[1,2,3\]  
> 输出:  
> \[  
> \[3\],  
> \[1\],  
> \[2\],  
> \[1,2,3\],  
> \[1,3\],  
> \[2,3\],  
> \[1,2\],  
> \[\]  
> \]

## 题目分析 ##

Ps. 第一感觉是使用回溯策略，但是…回溯策略这么经典~~有细节又想不清了 ~~还是放到后面吧。“暴力实现”，才称得上直接实现?。

幂集的性质我们都很熟悉——“从全空到全满”。而且幂集的性质是 N = 2^(k - 1)：  
e.g. 空——1个子集，1个元素——2个子集，2个元素——4个子集，……

## 解题分析 ##

也就是说，**每增加一个元素，新的子集总数是未添加前的两倍/增加了一倍**  
——>这就很好统计/表示了：**每次加入一个元素就扩充subset的长度，直到所有元素添加完毕**。

## 代码实现 ##

class Solution {
        
    public:
        vector<vector<int>> subsets(vector<int>& nums) {
        
            vector<vector<int>> subset;
            subset.push_back({
        });   // 初始化解空间并置空
            for(int i = 0; i < nums.size(); i++)
            {
        
                int k = subset.size();  // 当前子集总个数 用于后续扩展
                
                // 逐个复制原有子集，添加新元素，然后逐个添加在容器尾部
                for(int j = 0; j < k; j++)
                {
        
                    vector<int> past = subset[j];
                    past.push_back(nums[i]);
                    subset.push_back(past);
                }
            }
            return subset;
        }
    };

![在这里插入图片描述][20190917222801594.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]  
复杂度分析：

*  时间复杂度：O(N^2)
 *  空间复杂度：O(2^N)

还不错，但还没结束。

## 其他方式 ##

一、回溯策略  
经典的 躲不开的 回溯策略。  
前几天 [精选50题之 46. 全排列][50_ 46.] 中就使用了回溯策略，嗯，结合上一个实现，修改一下就可以实现。

class Solution {
        
    public:
        vector<vector<int>> subsets(vector<int>& nums) {
        
            vector<vector<int>> subset;
            vector<int> past;
            backtrack(subset, past, nums, 0);
            return subset;
        }
        void backtrack(vector<vector<int>> &subset, vector<int> past, vector<int>& nums, int depth)
        {
        
            {
        
                if(past.size() <= nums.size())
                    subset.push_back(past);
            }
            for(int i = depth; i < nums.size(); i++)
            {
        
                past.push_back(nums[i]);
                backtrack(subset, past, nums, i+1);
                past.pop_back();
            }
        }
    };

![在这里插入图片描述][20190917225101505.png]  
复杂度分析：

*  时间复杂度：?
 *  空间复杂度：O(2^N)

## 特殊方式 ##

一、  
最初分析时，曾写道

> 幂集的性质我们都很熟悉——“从全空到全满”

那么，如果我们可以“定义”出全部状态，直接返回即可。  
这就是 **位运算法**  
[连接1][1] [连接2][2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 1]  
参考代码

class Solution {
        
    public:
        vector<vector<int>> subsets(vector<int>& nums) {
        
            vector<vector<int>>subset_set;
            int subset_num=1<<nums.size();
            for(int i=0;i<subset_num;i++){
        
                vector<int>subset;
                for(int j=0;j<nums.size();j++){
        
                    if(i&1<<j){
        
                        subset.push_back(nums[j]);
                    }
                }
                subset_set.push_back(subset);
            }
            return subset_set;
        }
    };

二、  
看提交范例，0ms的居然是DFS，这……?

class Solution {
        
    public:
        void dfs(int i, vector<int> nums, vector<int> &tmp, vector<vector<int>> &res)
        {
        
            if(i >= nums.size())  return;
            tmp.push_back(nums[i]);
            res.push_back(tmp);
            dfs(i+1,nums,tmp,res);
            tmp.pop_back();
            dfs(i+1,nums,tmp,res);
            
        }
        vector<vector<int>> subsets(vector<int>& nums) {
        
            vector<vector<int>> res;
            vector<int>tmp;
            res.push_back(tmp);
            dfs(0,nums,tmp,res);
            return res;
        }
    };

先贴上来

## 写在最后 ##

晚安

[Link 1]: https://leetcode-cn.com/problems/subsets/
[20190917222801594.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/7fe6fdd2ac31482e86ff10556189832e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/3652fa4eebed46c8b755f1b6809aa8be.png
[50_ 46.]: https://blog.csdn.net/weixin_41728431/article/details/100711834
[20190917225101505.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/aaf47bc45b2041c397f996c73f7cb7d0.png
[1]: https://www.cnblogs.com/huashanqingzhu/p/6536484.html
[2]: https://www.cnblogs.com/kubidemanong/p/10880482.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/dcae9ea1679640dba0b2cd0d62d0092e.png