龙岩e龙岩网_南京列表网免费发布信息_最新网站推广方法_网络营销策划案怎么写

给你一个 只包含正整数 的 非空 数组 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$

---

思路：动态规划

• 找两个子集，使得两个子集的和相等，相当于找，在 [0, n-1] 取元素，每个元素最多取一次，使得取到的元素和恰好 = 总和的一半（sum/2）
• 所以题目就转换成了，在 [0, n-1] 取元素，使得和恰好等于 sum/2
• 可以看出类似于 0/1 背包问题，和 0/1 背包的区别在于
• 一个是不超过 背包容量，一个是恰好等于 背包容量
• 一个是求 max 最大值，一个是求是否存在 bool 值
• 所以类别 0/1 背包，可以定义当前动态规划 问题
• f[i][j]：在[0…i] 中取元素，每个元素最多取一次，是否和恰好能凑够 j
• 状态转移方程：
  • 如果当前下标为 i 的元素，nums[i] > j，则肯定不能取当前元素，所以 f[i][j] = f[i-1][j]（即去掉当前第 i 个元素，在 [0…i-1] 中取元素，是否恰好凑够 j）
  • 如果 nums[i] <= j，则可以取当前元素/不取当前元素，f[i][j] = f[i-1][j-nums[i]] | f[i-1][j]，即不取当前元素的话，同上，取当前元素的话，是否能凑够 j，则需要判断，去掉当前元素在 [0…i-1] 中取，是否恰好能凑够 j - nums[i]
• 注意：
  • 对于 f[i][0]，即从 [0…i] 中取，恰好能凑够 0 的位置，一定是 true，因为凑 0 不需要去任何元素即可
  • f[0][nums[0]] = true，即只有第一个元素时，只能凑够 j = nums[0]（这里这样特判，是因为后面遍历的时候可以 i 从 1 开始，状态转移方程中 f[i-1][x]，其中的 i - 1 就不用特殊判断了）

class Solution {
public:// 从前i个物品中选，总和恰好等于j的集合// 是否能恰好凑够 jbool f[210][20010];bool canPartition(vector<int>& nums) {int n = nums.size();if(n < 2) return false;int sum = 0, mN = 0;for(int i = 0; i < n; i++){sum += nums[i];mN = max(mN, nums[i]);}if(sum % 2) return false;sum /= 2;if(mN > sum) return false;for(int i = 0; i < n; i++)f[i][0] = true;f[0][nums[0]] = true;for(int i = 1; i < n; i++){for(int j = 1; j <= sum; j++){f[i][j] = f[i-1][j];if(nums[i] <= j) f[i][j] = f[i][j] | f[i-1][j-nums[i]];}}return f[n-1][sum];}
};