C++ 2D DP solution, essentially the subset sum problem, why does Python get MLE but C++ doesnt? Please fix this.


  • 0
    I

    I believe this is the standard soln that interviewer would expect. I tried the same algo in python but i got a MLE, but C++ works. Why?

    public:
        bool canPartition(vector<int>& nums) {
            if (!nums.size())
                return false;
            int num_sum = 0;
            for (auto n: nums) {
                num_sum += n;
            }
            
            if (num_sum % 2 != 0)
                return false;
                
            int target_sum = num_sum / 2;
            vector<vector<bool>> subset_sum(nums.size() + 1, vector<bool> (target_sum + 1, false));
            
            for (int i = 0; i <= nums.size(); i++) {
                for (int s = 0; s <= target_sum; s++) {
                    if (s == 0)
                        subset_sum[i][s] = true;
                    else if (i >= 1) {
                        subset_sum[i][s] = subset_sum[i-1][s] || (nums[i-1] <= s && subset_sum[i-1][s - nums[i-1]]);
                    }
                }
            }
            
            return subset_sum[nums.size()][target_sum];
        }
    };

  • 0

    @IWantToPass This is just fixed. Your python equivalent solution should get Accepted too, thanks.


Log in to reply
 

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