本文主要是介绍【打卡第240道】【动态规划DP01背包】【leetCode高频】：416. 分割等和子集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1、题目描述
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
2、算法分析
这个是一道经典的01背包题目。
注意：01背包的题目是解决的是元素只能使用一次的情况。
思路：
题目中说，nums数组中分成两个子集，并且两个子集的和是相等的。
那么这样，背包的容量是数组一半的和。如果总和是奇数，则返回false；
加下来就是dp的处理
1、定义dp数组
int [] dp = new int[sum / 2 + 1]，表示的是在容量为sum的一半的背包里，找到最大的元素和。
2、初始化数组
dp[0] = 0;
3、确定关系式子
找到最大的和。这个式子怎么得出来的。具体看01背包的知识。
dp[j] = Math.max(dp[j],dp[j - nums[i]] + nums[]);
4、遍历
先遍历物品，后遍历背包大小。注意，一维数组的遍历要逆序遍历，防止重复添加。
最后返回的是dp[target] == target，因为找的就是和的一半。
3、代码实现
class Solution {public boolean canPartition(int[] nums) {if(nums == null || nums.length == 0){return false;}// 如果总和是奇数，则返回falseint sum = 0;// 求和for(int i = 0;i < nums.length;i++){sum += nums[i];}if(sum % 2 == 1){return false;}int target = sum / 2;// dp[i] : dp[j]表示 背包总容量是j，最大可以凑成j的子集总和为dp[j]int[] dp = new int[target + 1];for(int i = 0;i < nums.length;i++){for(int j = target;j >=nums[i];j--){// 重量是nums[i],价值也是nums[i]dp[j] = Math.max(dp[j],dp[j - nums[i]] + nums[i]);}}return dp[target] == target;}
}这篇关于【打卡第240道】【动态规划DP01背包】【leetCode高频】：416. 分割等和子集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
