LeetCode 热题 100_子集（56_78_中等_C++）（回溯）(ans.clear())

题目描述：

给你一个整数数组 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 中的所有元素 互不相同

题解：

解题思路：

思路一（递归（回溯））：

1、当解决全排列和子集组合等问题时，我们可以优先想到回溯解决此类问题，在解决此类问题时我们最好先画一个递归树帮助我们进行分析。
以示例 1画递归树如下：

2、具体思路如下：
① 通过递归树我们可以分析出，递归树的每个结点都会生成一个子集。
② 在进行递归的时候，当一个元素选取之后，剩余元素的选取需从此元素之后选取。
③ 在进行回溯时我们需要将刚放入的元素去掉，以便放入其他元素。

3、复杂度分析
① 时间复杂度：n*2ⁿ ，n代表整数数组中元素的个数，递归树中的每个结点都会遍历一遍（每个结点就是一个子集），结点的总数为2ⁿ。
每次递归调用时，都需要将当前的 path（当前子集）添加到 ans 中这个操作的时间复杂度是 O(k)，其中 k 是当前 path 的长度。因为 path 中的元素数目在最坏情况下为 n，所以生成每个子集的时间复杂度是 O(n)。
所以时间复杂度为n * 2ⁿ。
② 空间复杂度：O(n)。去除返回答案的空间，还有path和函数递归调用使用的空间。path最大存储最大的子集也就是O(n),函数递归调用最大的深度也是最大子集的大小O(n)。

代码实现

代码实现（思路一（递归（回溯）））：

#include<iostream>
#include<vector>
using namespace std;

//思路一（递归（回溯））
class Solution {
private:
    //ans存储所有子集
    vector<vector<int>> ans;
    //path存储单个子集
    vector<int> path; 
    void backtracking(vector<int>&nums,int startIndex){
        //在每个树的结点处都会生成一个子集，所以要先记录再进行递归
        ans.emplace_back(path);
        //当一个元素选取之后，下一个元素的选取需从此元素之后选取
        for (int i = startIndex; i <nums.size() ; i++)
        {
            //取元素
            path.emplace_back(nums[i]);
            //当i取了之后，我们需要取i之后的元素组成子集(防止出现全排列的情况)
            backtracking(nums,i+1);
            //放回元素，取下一个元素
            path.pop_back();
        }
    }

public:
    vector<vector<int>> subsets(vector<int>& nums) {
        //清空 ans和path 向量。防止多次调用时残留上次调用的数据
        ans.clear();
        path.clear();
        backtracking(nums,0);
        return ans;
    }
};

int main(){
    vector<int> nums={1,2,3};
	//生成a的所有子集
    Solution s;
    vector<vector<int>> ans= s.subsets(nums);
    
    //输出a的所有子集
    for (auto &nums : ans)
    {
        cout<<"[";
        for (auto &i : nums)
        {
            cout<<i;
            if (i==nums.back()) continue;
            cout<<" ";
        }
        cout<<"] ";
    }
    
    return 0;
}

部分代码解读

ans.clear()

//清空 ans和path 向量。防止多次调用时残留上次调用的数据
ans.clear();
path.clear();

如果没有这行 ans.clear();，在多次调用 subsets 的情况下，ans 会保留上一次计算的结果，导致返回的子集包含之前的内容，这样就不符合期望的行为了。

ans.clear(); 的时间复杂度是 O(1):
clear() 的作用是清空 ans 向量中的所有元素，但并不释放内部存储的内存（即保留了原本分配的容量）。因此，这个操作的时间复杂度是 O(1)，只是调整了内部的 size 属性，而不涉及逐一删除元素的操作。

参考链接，其中有视频讲解很不错
LeetCode 热题 100_子集（56_78)原题链接
欢迎大家和我沟通交流(✿◠‿◠)