题目：
Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Note:
Each of the array element will not exceed 100.
The array size will not exceed 200.
Example1：
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example2：
Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.
思路：
该题采用动态规划的思路来做。
- dp[i][n] : 代表i个物品在体积为n的情况下的最大值。
- 状态转移方程:
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - nums[i]] + nums[]i);
注意：
数组中所有数的和必须为偶数。如果为奇数则返回false。是偶数则和sum除以2。求出n个物品在体积为sum/2的情况下的最大值。
如果dp[n][sum/2] == sum/2返回True，否则返回False。
代码：
public boolean canPartition(int[] nums) {
boolean flag = false;
if(nums == null || nums.length == 0)
return flag;
int sum = 0;
for(int num:nums){
sum += num;
}
if(sum % 2 == 1)
return false;
sum /= 2;
int [][] dp = new int [nums.length][sum + 1];
for(int i=nums[0];i<sum+1;i++){
dp[0][i] = nums[0];
}
for(int i=1;i<nums.length;i++){
for(int j=nums[i];j<sum+1;j++){
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-nums[i]] + nums[i]);
}
}
return dp[nums.length - 1][sum] == sum ? true : false;
}
