# Java dynamic programming (fastest)

• Dynamic programming solution:
Calculating the sum of all members in the array, and find if is there any subsets of the array has sum equal to sum/2
The general DP formula is:

dp[n][W] = dp[n - 1][W - a[n-1]] || dp[n - 1][W]

Detail solution:

public class Solution {

public boolean canPartition(int[] nums) {
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
}
if (sum %2 != 0) return false;
sum /= 2;

boolean dp[][] = new boolean[nums.length + 1][sum + 1];

for (int i = 0; i < nums.length + 1; i++) {
for (int j = 0; j < sum + 1; j ++) {
if (i == 0 || j == 0)
dp[i][j] = false;
}
}

dp[0][0] = true;

for (int i = 1; i < nums.length + 1; i++) {
for (int j = 1; j < sum + 1; j++) {
if (j >= nums[i- 1])
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i-1]];
else
dp[i][j] = dp[i - 1][j];
}
}

return dp[nums.length][sum];
}
}

• Is One Dimension Array sufficed? Is it a must to use TWO Dimension Array for this problem ?

• Intuitively I think two dimensional array makes it easy for me to understand the problem, so I go with two dimensional array.

• @phhoang :D That's fine. There are quite a few threads using the 1D array. As far as I know, they'd work as well.

• Well done! It became the typical backpack question with your DP formula.

• Good solution.
But I got Memory limitation exceed when 2D array. So I use 1D Array and it is accepted.

class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum & 1) return false;
sum >>= 1;
vector<int> dp(sum+1, false);
dp[0] = true;
for (int i = 1; i <= nums.size(); i++ ) {
for (int j = sum; j >= 1; j--) {
if (j >= nums[i-1]) {
dp[j] = dp[j] || dp[j-nums[i-1]];
} else {
dp[j] = dp[j];
}
}
}
return dp[sum];
}
};

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