题目链接：416. 分割等和子集 - 力扣（LeetCode）

判断数组能否被分成两个和相等的子数组，先求数组的和sum，即变成能不能找到一个组合的和是sum/2，每个数最多只能被选择一次，即0-1背包问题

0-1背包状态转移方程：如果选择，那么空间减少，价值增加，dp[i]为空间为i的最大价值

dp[j]=max(dp[j],dp[j-weight[i]]+value[i])

本问题：dp[i]为是否存在和为i的子集，如果选择当前元素，变成是否存在和为i-num的子集

dp[i]=dp[i] || dp[i-num]

特别注意如果sum是奇数，那么sum/2不是整数肯定不存在

class Solution {
public:bool canPartition(vector<int> &nums) {int sum = 0;for (auto &num: nums)sum += num;if (sum & 1)return false;int target = sum / 2;vector<bool> dp(target + 1);dp[0] = true;for (auto &num: nums) {for (int i = target; i >= num; --i) {dp[i] = dp[i] || dp[i - num];}}return dp[target];}
};