【0-1背包】力扣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:bool canPartition(vector<int>& nums) {int n = nums.size();if(n < 2){return false;}int sum = 0;int maxNum = 0;for(int i = 0; i < n; i++){sum += nums[i];maxNum = max(maxNum, nums[i]);}if(sum & 1){return false;}int target = sum / 2;if(maxNum > target){return false;}vector<int> dp(target + 1, 0);dp[0] = true;for(int i = 0; i < n; i++){for(int j = target;j >= nums[i]; j--){dp[j] |= dp[j-nums[i]];}}return dp[target];}
};
首先先判断数组可以被分割成等和子集的必要特征，当数组大小小于2的时候，返回false。接着计算出总和sum和最大的元素maxNum，当sum是奇数的时候，返回false，当最大元素大于sum / 2的时候，也返回false。
dp[j] |= dp[j-nums[i]];
使用或运算，dp[j] 中的 j 代表的是当前要检查的子集和，也就是在给定的数组中，是否可以找到一个子集，使得这个子集的元素和等于 j。
在遍历数组 nums 时，对于每个元素 nums[i]，我们从 target 开始逆序遍历到 nums[i]，并更新 dp[j]：
例如，当我们处理 nums[i] = 5 时：
我们会检查 dp[11] 是否可以由 dp[11-5] 转化而来，即 dp[6] 如果为 true，那么 dp[11] 也可以变为 true。类似地，dp[6] 可以由 dp[6-5] = dp[1] 转化而来。通过这种方式，dp[j] 会被不断更新，最终 dp[target] 如果为 true，说明存在一个子集和等于 target。