参考文章：代码随想录https://programmercarl.com/0416.%E5%88%86%E5%89%B2%E7%AD%89%E5%92%8C%E5%AD%90%E9%9B%86.html
一、题目
给你一个 只包含正整数 的 非空 数组 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
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/partition-equal-subset-sum/
二、题解
首先要想到，两个子集的元素和相等，即每个子集的元素和都等于数组元素和的一半
由此又可想到，数组元素和必须为偶数，若为奇数函数可直接返回 false，因为若为奇数则除以 2 除不尽。或者说因为数组每个元素都是整数，两个子集的元素和也必定是整数，而且两个子集元素和相等，那么数组元素和必定为偶数。
在我看来，本题难点在于转换成 01 背包问题。
以题目中示例一为例，求 nums 能否分割成两个等和子集，就是求 nums 数组中是否有元素相加等于 11。我们可以把 nums 数组中的元素的值看成物品的重量，11 视为背包最大容量，则题目就是给定一组物品重量值，问能否装满容量为 target 的背包（target 为数组元素和的一半）？
由于每个元素只能使用一次，所以这是个零一背包问题
如何判断背包是否装满呢？我们可以令每个数组元素的数值既是物品的重量也是物品的价值，即每个物品的单位价值为 1。当背包装满时，背包重量为 target，背包的最大价值也必然为 target。故判断条件为：dp[target] == target
想清楚后，再用动归五部曲分析就比较简单了
dp 数组以及下标的含义：dp[j] 表示 背包总容量（所能装的总重量）是 j，放进物品后，背的最大重量为 dp[j]
要注意的是，由于物品重量和价值相同，所以 weight[i] = value[i] = num[i]，所以递归公式为：dp[j] = max(dp[j], dp[j – nums[i]] + nums[i]);
dp 数组初始化时，如果题目给的价值都是正整数，那么非 0 下标都初始化为非负整数里的最小值 0 就可以了，如果题目给的价值有负数，那么非 0 下标就要初始化为负无穷。这样才能让 dp 数组在递推的过程中取得最大的价值，而不是被初始值覆盖了。本题题目中 只包含正整数的非空数组，所以非 0 下标的元素初始化为 0 就可以了。
遍历顺序：物品遍历的 for 循环放在外层，遍历背包的 for 循环放在内层，且内层 for 循环倒序遍历！
三、代码
public class T416 {
//一维滚动数组
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums)
sum += num;
if (sum % 2 != 0)
return false;
int target = sum / 2;
int[] dp = new int[target+1];
for (int i = 0; i < nums.length; i++) {
for (int j = target; j >= nums[i]; j--) {
dp[j] = Integer.max(dp[j],dp[j-nums[i]]+nums[i]);
}
//剪枝一下，每一次完成内层的for-loop，立即检查是否dp[target] == target
if(dp[target] == target)
return true;
}
/*if (dp[target] == target) {
return true;
}else {
return false;
}*/
return dp[target] == target;
}
//二维dp数组
public boolean canPartition(int[] nums) {
int len = nums.length;
int sum = 0;
for (int num : nums){
sum += num;
}
if(sum % 2 == 1){
return false;
}
int target = sum / 2;
int[][] dp = new int[len][target + 1];
for(int j = nums[0]; j <= target; j++){
dp[0][j] = nums[0];
}
for(int i = 1; i < len; i++){
for(int j = 1; j <= target; j++){
if (j < nums[i])
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
}
}
return dp[len - 1][target] == target;
}
}