# c++ solution with dynamic programming

• ``````bool canPartition(vector<int>& nums) {
int sum = 0;
for (auto i : nums)
sum += i;
if (sum % 2)
return false;
// dp[i][j] == true iff there is a subset of the first j numbers such that the sum of the subset is i
bool dp[sum/2+1][nums.size()+1];
for (int i = 0; i < sum/2 + 1; i++) {
for (int j = 0; j < nums.size() + 1; j++) {
dp[0][j] = true; // sum of an empty set is 0
dp[i][0] = false; // numbers are positive
}
dp[0][0] = true;
}

for (int i = 1; i < sum/2 + 1; i++)
for (int j = 1; j < nums.size() + 1; j++)
// we either take the last element or don't
dp[i][j] = (i > nums[j-1]) && (dp[i][j-1] || dp[i - nums[j-1]][j-1]);

return dp[sum/2][nums.size()];
``````

• For the second part of this line`dp[i][j] = dp[i][j-1] || dp[i - nums[j-1]][j-1];` I think you'd better add the condition`if(i >= nums[j - 1])` to check if `i - nums[j - 1]` is valid.

• @xietao0221 You are absolutely right!

• my solution with Dp is easy to understand.

class Solution {
public:
bool canPartition(vector<int>& nums) {

``````   int sum = 0;

for(int i=0; i<nums.size(); i++) sum += nums[i];

if( sum & 0x01 ) {  return false; }

int target = sum >> 1;

vector<bool> res(target+1, 0);
//printf("target = %d", target);

res[0]  = true;

for(int i=1; i<=target; i++)
{
for(int j=0; j<nums.size(); j++)
{
if(nums[j] <= i  && !res[i] ) res[i] = res[i-nums[j]];
}
}

return res[target];

}
``````

};

• @blueday0594
Your source will fail in the case [2, 6].
In this case, `target` is 4. You source will return `res[4] == true` using 2 + 2.
However, the expected answer is `false`.

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