Please help... Cannot find the bug in the code


  • 0
    Z

    Hi, the code passed 103/104 tests but failed on the last one. I tried running the last test case by manually copying it to the 'Custom Testcase' and clicked 'Run', it gave the correct result (which is false), and I also tried running the program on my machine and the answer is also false).

    I am aware of this article Note: is Run Code inconsistent with Submit Solution? If you are using global variables or C/C++, check this out, but still I could not find where the bug is. Can any one please help find out why it's producing wrong result for the very last testcase? The program is simply a 0-1 backpack DP algorithm. Thanks in advance!!!

    Test case:
    [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,100]
    
    class Solution {
    public:
        bool canPartition(vector<int>& nums) {
            if (nums.size() < 2) return false;
            int sum = accumulate(nums.begin(), nums.end(), 0);
            if (sum % 2 != 0) return false;
            
            // DP[i][j]: can we get j from first i items
            // DP[i][j] = DP[i-1][j] || DP[i-1][j-nums[i]]  // pick nums[i] or not
            //auto it = minmax_element(nums.begin(), nums.end());
            int target = sum / 2;
            vector<vector<bool>> DP(nums.size() + 1, vector<bool>(target + 1, false));
            for (int i = 0; i <= nums.size(); ++i) {
                DP[i][0] = true;  // pick nothing
            }
            for (int i = 1; i <= target; ++i) {
                DP[0][i] = false;
            }
            for (int i = 1; i <= nums.size(); ++i) {
                for (int j = 1; j <= target; ++j) {
                    if (j >= nums[i]) {
                        DP[i][j] = DP[i-1][j] || DP[i-1][j-nums[i]];
                    } else {
                        DP[i][j] = DP[i-1][j];
                    }
                }
                if (DP[i][target]) {
                    return true;
                }
            }
            return DP[nums.size()][target];
        }
    };
    

Log in to reply
 

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