Leecode热题100-416.分割等和子集
给你一个 只包含正整数 的 非空 数组 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
比较简单的题，直接上代码
class Solution {public static boolean canPartitionSimple(int[] nums) {/*** 先算一下元素的和是多少*/int sum = 0;for(int num : nums) {sum += num;}/*** 如果sum是个奇数，那直接返回false即可*/if((sum & 1) == 1){return false;}/*** 如果是偶数，我们的目标是sum的一半*/int target = sum >> 1;return canGetTarget(nums, 0, target);}public static boolean canPartition(int[] nums) {/*** 先算一下元素的和是多少*/int sum = 0;for(int num : nums) {sum += num;}/*** 如果sum是个奇数，那直接返回false即可*/if((sum & 1) == 1){return false;}int n = nums.length;/*** 如果是偶数，我们的目标是sum的一半*/int target = sum >> 1;/*** 根据递归，我们知道有两个可变参数：index从0到n，targetNow从0到target*/boolean[][] dp = new boolean[n + 1][target + 1];/*** 如果index=n，那只有targetNow=0的时候才是true,默认为false，所以只需要设置dp[n][0]=true*/dp[n][0] = true;/*** index行依赖于index+1行，所以从后往前遍历，n行已经遍历过了，所以现在从n-1开始* targetNow同行无依赖，所以从0或者从target开始都无所谓*/for(int index = n - 1; index >= 0; index --) {for(int targetNow = 0; targetNow <= target; targetNow ++) {/*** 如果没有越界，当前的位置可以选择要或者不要* 这两种选择只要能有一种是正确的，那就是正确的*//*** 第一种选择：要，targetNow减去当前的* 这种我们需要进行剪枝，如果targetNow - nums[index]小于0了，那后面无论如何也不可能，因为都是正数* 正数不可能拼出负数*/boolean p1 = targetNow - nums[index] < 0? false : dp[index + 1][targetNow - nums[index]];/*** 第二种选择，不要,targetNow不变*/boolean p2 = dp[index + 1][targetNow];dp[index][targetNow] = p1 | p2;}}return dp[0][target];}/*** 递归函数的含义：当前要决策index位置的数要不要，0~index-1的所有数都已经做完决策，不需要关心* 0~index-1之后还剩下targetNow需要拼出来* @param nums* @param index* @param targetNow* @return*/public static boolean canGetTarget(int[] nums, int index, int targetNow) {/*** 如果index已经越界了，那targetNow如果是0，就是正确的尝试，否则不是*/if(index == nums.length) {return targetNow == 0? true : false;}/*** 如果没有越界，当前的位置可以选择要或者不要* 这两种选择只要能有一种是正确的，那就是正确的*//*** 第一种选择：要，targetNow减去当前的* 这种我们需要进行剪枝，如果targetNow - nums[index]小于0了，那后面无论如何也不可能，因为都是正数* 正数不可能拼出负数*/boolean p1 = targetNow - nums[index] < 0? false : canGetTarget(nums, index + 1, targetNow - nums[index]);/*** 第二种选择，不要,targetNow不变*/boolean p2 = canGetTarget(nums, index + 1, targetNow);return p1 | p2;}
}效果一般，回头再优化吧，先解题
