LeetCode

您所在的位置：网站首页 › 平均数分为 › LeetCode

LeetCode

2023-09-23 12:03| 来源: 网络整理| 查看: 265

1.分割等和子集

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意:

每个数组中的元素不会超过 100数组的大小不会超过 200

示例 1:

输入: [1, 5, 11, 5] 输出: true 解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:

输入: [1, 2, 3, 5] 输出: false 解释: 数组不能分割成两个元素和相等的子集. 题解：分割等和子集，那就先求和，再平分。如果不能平分，那就直接返回false，否则，问题就变成了判断数组是否存在若干个元素求和正好等于数组和的一半，那就直接遍历所有的结果，深搜解决，可以，这种方式很容易想到。还有一种方法是将这个问题转化为背包问题，使背包的大小为数组和的一半，问题转化为是否存在数组元素使背包正好被装满，也就是最优解是数组和的一半。

深搜解法：

class Solution { public boolean canPartition(int[] nums) { int sum=0; for(int n:nums) sum+=n; if(sum%2!=0) return false; return subsetSum(nums,sum>>>1); } public boolean subsetSum(int[] nums, int s) { boolean[] dp = new boolean[s + 1]; dp[0] = true; for (int n : nums){ for (int i = s; i >= n; i--){ dp[i] =dp[i]||dp[i - n]; } if(dp[s]) return true; } return dp[s]; } }

背包解法：

class Solution { public boolean canPartition(int[] nums) { int n=nums.length; int sum=0; for(int i=0;i

【本文地址】

LeetCode

LeetCode

今日新闻

推荐新闻