求这段生成所有子集的C++代码的时间复杂度及空间复杂度验证

待分析代码 #

class Solution {
private:
    void solve(vector<int>& nums, int index, vector<vector<int>> &ans, vector<int> v) {
        if (index >= nums.size()) {
            ans.push_back(v);
            v.clear();
            return;
        }
        //exclude
        solve(nums, index + 1, ans, v);
        //include
        int val = nums[index];
        v.push_back(val);
        solve(nums, index + 1, ans, v);
    }

public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int index = 0;
        vector<int> v;
        vector<vector<int>> ans;
        solve(nums, 0, ans, v);
        return ans;
    }
};

提问内容 #

我正在分析这段生成所有子集的C++代码的复杂度，我认为其空间复杂度为O(n)，理由是函数调用栈的最大占用空间等于n，且每个函数仅复制数组指针，占用常数空间，但不清楚其时间复杂度，特此咨询。

时间复杂度分析 #

• 对于包含n个元素的数组，总共有2ⁿ个子集，这是子集的总数。
• 每个子集生成时都会执行ans.push_back(v)操作，该操作的时间开销为O(k)（k是当前子集的元素数量，因为需要复制v中的所有元素到ans）。
• 计算所有子集的元素总数：每个元素会出现在2ⁿ⁻¹个子集中（每个元素有选/不选两种状态，剩余n-1个元素任意组合共2ⁿ⁻¹种），因此总元素数为n×2ⁿ⁻¹。
• 综上，这段代码的时间复杂度为O(n×2ⁿ)。

空间复杂度确认 #

你对空间复杂度的分析是正确的：

• 递归调用栈的最大深度为n（从index=0递归到index=n），栈空间占用O(n)。
• 若不考虑存储结果的ans（输出空间），仅计算算法的额外空间，复杂度为O(n)；若包含输出空间，总空间复杂度为O(n×2ⁿ)，你的分析聚焦于调用栈和额外空间，结论准确。

内容的提问来源于stack exchange，提问作者Tanuj