題目：
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.
思路：
該題采用動態(tài)規(guī)劃的思路來做巨朦。
- dp[i][n] : 代表i個物品在體積為n的情況下的最大值。
- 狀態(tài)轉(zhuǎn)移方程:
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - nums[i]] + nums[]i);
注意：
數(shù)組中所有數(shù)的和必須為偶數(shù)。如果為奇數(shù)則返回false。是偶數(shù)則和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;
}
