力扣【416. 分割等和子集】详细Java题解（背包问题）

首先我们可以求出数组和，当我们找到一个子集中元素的和为数组和的一半时，该就说明可以分割等和子集。
对于该问题我们可以转换成背包问题，求 数组里的元素 装入 数组和的一半大小的背包 能取得的最大值。
然后注意可以剪枝的地方。

代码：

class Solution {public boolean canPartition(int[] nums) {//计算数组的和int sum =0;for(int num:nums) sum += num;if(sum%2 != 0) return false; //如果和为奇数，那就不符合sum /= 2;int[][] dp = new int[nums.length+1][sum+1]; //dp[i][j]表示遍历到前i个物品时，j容量背包能转的最大值//第0行就是还没有物品加入计算，初始化为0for(int i=0;i<sum+1;i++){dp[0][i] = 0; }//开始动规计算for(int i=1;i<=nums.length;i++){for(int j=1;j<=sum;j++){if(nums[i-1] <= j) dp[i][j] = Math.max(nums[i-1] + dp[i-1][j-nums[i-1]],dp[i-1][j]);else dp[i][j] = dp[i-1][j];}if(dp[i][sum] == sum) return true; //剪枝}//结果判断if(dp[nums.length][sum] == sum){return true;}return false;}
}

不过我们其实可以用一维数组来做，因为我们的每次迭代其实只用到了dp数组的上一行。那我们可以用一个数组来进行滚动，不过遍历顺序得从后往前，因为我们迭代后面的物品时需要用到前面物品的值，且当容量大于当前遍历的物品时才迭代。
这样我们的代码更简洁且时间复杂度和空间复杂度都有改善。

class Solution {public boolean canPartition(int[] nums) {//计算数组的和int sum =0;for(int num:nums) sum += num;if(sum%2 != 0) return false; //如果和为奇数，那就不符合sum /= 2;int[] dp = new int[sum+1]; //第0行就是还没有物品加入计算，初始化为0for(int i=0;i<sum+1;i++){dp[i] = 0; }//开始动规计算for(int i=1;i<=nums.length;i++){for(int j=sum;j>=nums[i-1];j--){dp[j] = Math.max(nums[i-1] + dp[j-nums[i-1]],dp[j]);if(j==sum && dp[j] == sum) return true; //剪枝}}return false;}
}