难度中等
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。 注意: 1. 每个数组中的元素不会超过 100 2. 数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
思路1.0：在做石头对撞哪一题的方法可以用上。01背包滚动数组 limit = sum/2; dp[limit]：在容量上限为总重量一半时，能装入的最大重量。 sum%2!=0,return false; dp[limit]=max(dp[limit],dp[limit-value[i]]+value[i])
代码1.0（已完成）
class Solution { public: bool canPartition(vector<int>& nums) { int sum = 0; for (auto& i : nums) { sum += i; } if (sum % 2 != 0) return false; int limit = sum / 2; vector<int> dp(limit +1); for (auto& num : nums) { for (int i = limit; i >= num; --i) { dp[i] = max(dp[i], dp[i - num] + num); } } return dp[limit] == limit; } };