目录
问题描述
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
?
提示：
1 <= nums.length <= 200
1 <= nums[i] <= 100
要素提取
两个子集的元素和相等。
两个子集的元素和相等，那么整个数组元素的和一定是一个偶数。两个相等的偶数相加或者两个相等的奇数相加一定都是一个偶数。
子集的元素和
在一个集合中找到若干个数，使它的和恰好为某个值，每个元素都只能被使用一次。这是一个0-1背包问题。
难点突破（0-1背包在本题中的应用）
本题思路
0-1背包的特点是【每个数只能用一次】。解决的基本思路是【物品一个一个去选，容量也一点点去加】在加的过程中考虑保留或是丢弃这个物品。
本题初始化一个nums.length行，target + 1列的二维数组。len行表示物品的数量，target + 1列表示背包的容量。容量要 +1 是因为背包问题一般需要初始条件，本题的初始条件也就是当背包容量为0时，能装的物品数量也是0【没有物品能够装进去】。
状态定义与状态转移方程
状态定义：dp[i][j] 表示从数组[0,i]中挑选一些数字，使得这些数字的和恰好为 j。
状态转移方程：若物品容量等于当前容量那么一定是true。
选择不装第 i 个物品，如果选择在[0,i-1]这个子区间区间内已经有元素和等于 j 那么为true。
选择装第 i 个物品，在[0,i-1]这个子区间内有元素的和为 j-nums[i] 那么为true
注意事项：确保数组下标不能越界。i-1 要 大于等于 0 ，j-nums[i] 要大于等于0
当容量为 0 时，没有物品能装进去所以第一列全部为 false。
?
代码实现
class Solution {
boolean ans = false;
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;
}
int target = sum/2;
boolean[][] dp = new boolean[nums.length][target + 1];
for(int i = 0;i < target + 1;i++) {//容量为0时，没有物品能够放进去
dp[0][i] = false;
}
for(int i = 0;i < nums.length;i++) {
for(int j = 0;j < target + 1;j++) {
boolean b1 = false;
boolean b2 = false;
if (i-1 >= 0) {
b1 = dp[i-1][j];//在数组范围[0,i-1]中存在元素的和为j吗？
if (j - nums[i] >= 0) {
b2 = dp[i-1][j - nums[i]];//在数组范围[0,i-1]中存在元素的和为j-nums[j]吗？
}
}
dp[i][j] = b1 || b2 || nums[i] == j;
}
}
return dp[nums.length-1][target];
}
}
