recursion memory limit exceed for first test case


  • 0
    N

    My solution is recursion. Honestly, I am not quite clear about space complexity of my solution. And it failed at first case [1, 2, 3] due to "Memory limit exceed". Could anyone help tell me space complexity of below code?
    basic algorithm is use subarray[i - 1, size -1] 's subsets to get subarray[i, size - 1]'s subsets
    Thanks

    class Solution {
    public:
    // memory limit exceed
    vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> res;
    if (nums.size() == 0) {
    return res;
    }

        recursion(0, nums, res);
        return res;
    }
    
    void recursion(int k, vector<int>& nums, vector<vector<int>>& res) {
        // recursion exit/ basic case
        if (k == nums.size() - 1) {
            res.push_back(vector<int>(0));
            res.push_back(vector<int>(1, nums[k]));
            return;
        }
        // solve smaller case
        recursion(k + 1, nums, res);
        // recursive relationship
        for (int i = 0; i < res.size(); i++) {
            vector<int> cur(1, nums[k]);
            for (int j = 0; j < res[i].size(); j++) {
                cur.push_back(res[i][j]);
            }
            res.push_back(cur);
        }
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.