分割等和子集 Posted on 2021-09-04 00:00:00 2021-09-04 00:00:00 by Author 摘要 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。 # 分割等和子集 1. 题目描述 - 给你一个 **只包含正整数** 的 **非空** 数组 `nums` 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。 - **提示：** - `1 <= nums.length <= 200` - `1 <= nums[i] <= 100` 2. 示例描述 - 示例一 ```java 输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。 ``` - 示例二 ```java 输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。 ``` 3. 解题思路 - 首先对于本题来说，首先考虑数组的和是不是能够平分，如果不能平分，那么就直接无解，如果能够平分，才能继续下一步情况。那么怎么判断数组的和能不能平方尼，这非常简单，对于某一个数看能不能n等分，那么拿这个数取余n,如果余数为0那就可以n等分，如果不为0 ，那说明不能n等分，所有这里可以先算所给数组的和，如果和取余于2为0，那么就可以平方，否则就直接不能平分，返回false。 - 接下来，如果可以平分的话，那么对于所给的数组，只要找到其中几个数相加和为数组和的一半就可以了，这里可以用递归加回溯的思想去做，但是在leetcode上提交会出现时间超出限制，不能AC。那么这里就不能用递归和回溯的方法去解决了。 - 那么这里可以用DP去做(想问我为什么知道用DP去解决，你问我，我也不晓得，哈哈哈哈哈哈)。那么这道题怎么去构建DP，以及递推公式是什么尼。前提已经知道所给的数组可以拆分，那么我们就知道数组和的一半是多少了。那么就可以建立一个大小为所给数组和一半长度的数组dp[sum/2]（sum代表是数组的和）。其中dp[j]数组下标j代表的是j这个位置来说，所给数组的元素组成的和最大值是多少(前提是组成的最大值不能超过下标j)，那么当来到一个元素时，首先判断该元素是否大于下标j，如果大于下标j,那么该元素就不能参与组成下标j位置了，如果所给元素小于下标j,那么说明该元素可以参与该位置元素和的子集，如果该元素加入该位置组成和的集合中，如果和大于原来该位置的值的话，那么说明该元素可以加入，能够做出贡献。那么怎么知道该元素能否加入该位置和的集合中，那么就要看这个递推公式了:dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);这个公式具体理解在代码中有所体现，可以看着代码在结合注释理解理解。 - 以上是我自己的想法，我觉得自己还是没有讲清楚，但是自己心里知道是怎么回事，以后表达能力强了，再来雕琢一下。以下是这道题DP的具体解法。 4. 代码示例 ```java public boolean canPartition1(int[] nums) { //数组的总和 int sum = 0; for (int i = 0; i < nums.length; i++) { sum += nums[i]; } //如果总和为奇数，说明该数组不能被平分两半，之间返回false if (sum % 2 != 0) return false; //否则可以平方，那么平分后的目标值为target int target = sum / 2; //定义dp数组 int dp[] = new int[target + 1]; //以下就是本道题的精髓 //首先说明，dp数组中dp[j]中的j代表的是对于数字j来说，所给数组元素最多能够组成的和(sum)是多少(sum<=j)。 //这两个循环遍历的意思是 //对于数组的每一个元素，分别放入数组dp的每个下标中，首先放入的元素不能大于数组下标的值，这是为什么尼 //因为数组下标代表的是该位置所放的元素的值小于或者等于该下标的值(下标相当于0-1背包中的背包体积，所放的元素相等与某个物品的体积， // 也就是说物品的体积不能大于背包的体积才能放下去) //每个元素都分别放入不同下标下，那么dp每个位置代表的就是该体积下能容纳所给元素中和的最大值。 //其中递推公式:dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]); //代表的意思是当一个元素来的时候，如果能够放入该dp数组下标中，那么把这个元素放入进去的与原来改下标存的值比较，如果大于原来的值，那么就更新本次最大的值 //dp[j - nums[i]] + nums[i] 这个的意思是如果下标j能够装下所来的元素的时候，那么说明下标j>=nums[i],j-nums[i]，就是给所来的元素腾空位置 //也就是回到下标j-nums时，该位置能够容纳的最大值是多少，然后该位置的最大值加上nums[i]，也就是把nums[i]这个元素放入j中，那么此时下标j的值加上nums[i] //从而就能说明把该元素放入下标j中，放入后的最大值是多少。 for (int i = 0; i < nums.length; i++) { for (int j = target; j >= nums[i]; j--) { dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]); } } //最后看target下标中存的值是不是target本身，如果是本身的话，那么说明该数组可以平分为两份 return dp[target] == target; } ```
{{ item.content }}
{{ child.content }}