Why my DP solution gets MLE but my recursive solution is accepted


  • 0
    C

    I got a recursive solution accepted

    class Solution {
    public:
        vector<vector<int>> subsets(vector<int>& nums) {
            vector<vector<int> > res;
            res.push_back(vector<int>());
            if (!nums.size()) return res;
            sort(nums.begin(), nums.end());
            for (int idx = 0; idx < nums.size(); idx++){
                vector<int> current;
                subsetsHelper(nums, idx, res, current);
            }
            return res;
        }
        void subsetsHelper(vector<int>& nums, int idx, vector<vector<int> >& res, vector<int> current ){
            current.push_back(nums[idx]);
            res.push_back(current);
            for (int i = idx+1; i < nums.size(); i++) subsetsHelper(nums, i, res, current);
        }
    };
    

    However, my DP solution has MLE, which I don't understand why. It should use less memory than the recursive solution. Can you help me explain why?

    class Solution {
    public:
        vector<vector<int>> subsets(vector<int>& nums) {
            vector<vector<int> > res;
            res.push_back(vector<int>());
            sort(nums.begin(), nums.end());
            vector<int> tmp;
            for (int i = 0; i < nums.size(); i++){
                for (int j = 0; j < res.size(); j++){
                    tmp = res[j];
                    tmp.push_back(nums[i]);
                    res.push_back(tmp);
                }
            }
            return res;
        }
    };

Log in to reply
 

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