深圳网站建设世纪前线,360建筑网怎么样,营销网站建设大全,建设银行网站密码忘记了咋办416.分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集#xff0c;使得两个子集的元素和相等。
示例 1#xff1a;
输入#xff1a;nums [1,5,11,5]
输出#xff1a;true
解释#xff1a;数组可以分割成 [1, 5, 5] 和…416.分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。
示例 1
输入nums [1,5,11,5]
输出true
解释数组可以分割成 [1, 5, 5] 和 [11] 。示例 2
输入nums [1,2,3,5]
输出false
解释数组不能分割成两个元素和相等的子集。思路
回溯是一种解法但是会超时。
另一种将其转换成背包问题nums数组为物品重量及其价值背包容量为sum/2最后判断背包是否恰好被装满即可。
代码 public boolean canPartition(int[] nums) {if(nums null || nums.length 0) return false;int sumArrays.stream(nums).sum();if (sum%2!0)return false;int targetsum/2;int []dpnew int[target1];for(int i0;inums.length;i){for (int jtarget;inums[i];j--){dp[j]Math.max(dp[j],dp[j-nums[i]]nums[i]);}if (dp[target]target)return true;}return dp[target]target;}
