leetcode 78 子集

分手后的思念是犯贱 2022-08-28 11:50 169阅读 0赞

## 前言 ##

题目：[78. 子集][78.]

参考题解：[第78题. 子集-代码随想录][78_. _-]

--------------------

## 提交代码 ##

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

### 利用组合求子集 ###

之前做过[leetcode 77 组合][leetcode 77]。子集也可以转换成组合进行求解。

*  \[\]：从nums中选0个数
 *  \[1\],\[2\],\[3\]：从nums中选1个数
 *  \[1,2\],\[1,3\],\[2,3\]：从nums中选2个数
 *  \[1,2,3\]：从nums中选3个数

class Solution {
    private:
        vector<int> path;
        void backTracking(const vector<int>& nums, vector<vector<int>>& part_result, int n, int startIndex){
            // 从nums数字startIndex开始的位置，选择n个元素。结果保存在part_result
            // 递归出口
            if(path.size() == n){
                part_result.push_back(path);
                return;
            }
    
            for(int i=startIndex; path.size()+(nums.size()-i)>=n; i++){
                path.push_back(nums[i]);
                backTracking(nums,part_result,n,i+1);
                path.pop_back();
            }
        }
    
    public:
        vector<vector<int>> subsets(vector<int>& nums) {
            vector<vector<int>> result;
            for(int i=0; i<=nums.size(); i++){ // 从nums中选择0,1...nums.size个元素
                vector<vector<int>> part_result;
                backTracking(nums,part_result,i,0);
                for(auto path:part_result)
                    result.push_back(path);
            }
            return result;
        }
    };

### 保存回溯树的每个节点 ###

**图片和代码来讲参考题解**。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5aSnMTIzNOiNiQ_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]

class Solution {
    private:
        vector<vector<int>> result;
        vector<int> path;
        void backtracking(vector<int>& nums, int startIndex) {
            result.push_back(path); // 收集子集，要放在终止添加的上面，否则会漏掉自己
            for (int i = startIndex; i < nums.size(); i++) {
                path.push_back(nums[i]);
                backtracking(nums, i + 1);
                path.pop_back();
            }
        }
    public:
        vector<vector<int>> subsets(vector<int>& nums) {
            result.clear();
            path.clear();
            backtracking(nums, 0);
            return result;
        }
    };

[78.]: https://leetcode-cn.com/problems/subsets/
[78_. _-]: https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0078.%E5%AD%90%E9%9B%86.md
[leetcode 77]: https://blog.csdn.net/sinat_38816924/article/details/120442835
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5aSnMTIzNOiNiQ_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220828/952e0e9051fc42ada278862f6d4b27b1.png