给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。
提示：
1 <= nums.length <= 2001 <= nums[i] <= 100
思路：
本题采用动态规划的思路。dp[ j ] 表示容量为 j 的背包所能装的最大价值。本题中，数字的大小 既为物品的重量，又为物品的价值。令 target = sum /2 。sum 为 nums 数字各数之和。如果 sum 为奇数，则必不可能分为两个和相等的子集。往背包里面添加元素，每个元素的重量为 nums[ i ]，每个元素的价值为 nums[ i ]，当容量为 target 的背包里面的 最大价值 dp[ target ]为 target 时，说明能将一些元素装进一个背包里面，使得这些元素的 和为 sum 的一半，则说明必然可以将 nums 数组分为两个 和相等的子集。
递推公式：dp[ j ] = Math.max(dp[ j ]，dp[ j - nums[ i ] ]+ nums[ i ] ) 。
初始化：当 j = 0 时，背包的价值为0。同时把其他非 0 下标的 dp 值初始化为 0 避免初始值过大覆盖 计算出来的值 dp[ j - nums[ i ] ]+ nums[ i ] 。
遍历顺序：先遍历 物品(数字) i ，再遍历背包容量 j。注意 容量 j 要从 target 开始遍历，这样可以保证每个数字只添加一次，不重复添加。注意要先遍历 物品 i，再遍历背包容量 j，否则会导致 对于每个容量为 j 的背包，里面的最大价值是 物品 i 中 重量小于 j 的那一个物品的价值，即这时背包里面只能装一个元素。
代码：
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for(int x:nums){
sum += x;
}
if(sum%2!=0)return false;//如果sum为奇数，那么不能分割成两个元素和相等的子集
int target = sum/2;
//dp[j] 表示容量为j的背包的最大价值
int [] dp = new int[target+1];
for(int i=0;i<nums.length;i++){
// j>=nums[i]保证 背包可以放下当前物品（数字）
for(int j=target;j>=nums[i];j--){//j从容量最大开始计算，保证每个物品（数字）只加一次
dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);
}
}
if(dp[target]==target)return true;
return false;
}
}参考：代码随想录
