给定一个非空的正整数数组 nums ，请判断能否将这些数字分成元素和相等的两部分。
示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：nums 可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：nums 不可以分为和相等的两部分
背包问题解决
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0,maxNum = 0;
//当列表的总和不是偶数，那么不能分为两半
for(int num : nums){
sum += num;
maxNum = Math.max(maxNum,num);
}
if(sum % 2 == 1){
return false;
}
//如果其中一个数超了一半，那么这个列表也不能分为两半
int target = sum / 2;
if(maxNum>target)return false;
//背包问题 1,2,3,6为例子
// 0,1,2,3,4,5,6(总和)
//0 0,1,0,0,0,0,0
//1 0,1,1,1,0,0,0
//2 0,1,1,1,1,1,1
//3 0,1,1,1,1,1,1
boolean[][] dp = new boolean[nums.length][target+1];
for(int i=0;i<nums.length;i++){
dp[i][0] = false;
}
//第一行只有一个满足总和
dp[0][nums[0]] = true;
for(int i=1;i<nums.length;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];
}
}
}
return dp[nums.length-1][target];
}
}