• 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];
}
};
``````

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