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 <= 200
1 <= 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;}
}
效果一般,回头再优化吧,先解题