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

NP 完全问题（01背包）

特点是：「每个数只能用一次」。解决的基本思路是：物品一个一个选，容量也一点一点增加去考虑，这一点是「动态规划」的思想

对于「0-1 背包问题」而言就是「当前考虑到的数字选与不选」:

1. 不选择 nums[i]，如果在 [0, i - 1] 这个子区间内已经有一部分元素，使得它们的和为 j ，那么 dp[i][j] = true；
2. 选择 nums[i]，如果在 [0, i - 1] 这个子区间内就得找到一部分元素，使得它们的和为 j - nums[i]。
3. 状态转移方程为 dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]]

注意：观察状态转移方程，or 的结果只要为真，表格 这一列 下面所有的值都为真。

因此在填表的时候，只要表格的最后一列是 true，代码就可以结束，直接返回 true。（题解2）

题解1 二维DP

class Solution {
public:bool canPartition(vector<int>& nums) {int s = nums.size();int sumN = 0;for(auto&k : nums) sumN += k;// 总和不是偶数就不能分割成2 parts了if(sumN % 2) return false;sumN = sumN >> 1;// dp[i][j]: 从[0,i]范围内选取若干个正整数（可以是0个），是否存在一种选取方案使得被选取的正整数的和（物品重量总和）等于j（背包容量）// 如果dp.row = s,则需要设定dp[0][nums[0]]=true;后面的代码逻辑可以保持一致（有i-1）vector<vector<bool>> dp(s+1, vector<bool>(sumN+1, false));// 背包容量为0时 不放入就满足条件    for(int i = 1; i < s; i++){dp[i][0] = true;}for(int i = 1; i <= s; i++){for(int j = 1; j <= sumN; j++){if(j < nums[i-1])// 背包容量不足，不能装dp[i][j] = dp[i-1][j];else// 这样可以把状态传递到最后的元素// 要么装，要么不装（和上一个情况保持一致）dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];}}       return dp[s][sumN];}
};

题解2 空间优化DP（改为1D）

class Solution {
public:bool canPartition(vector<int>& nums) {int s = nums.size();int sumN = 0, maxN = 0;for(auto&k : nums){sumN += k;maxN = max(maxN, k);}if(sumN % 2) return false;sumN = sumN >> 1;// 剪枝if(maxN > sumN) return false;vector<bool> dp(sumN+1, false);dp[0] = true;for(int i = 0; i < s; i++){// 这里注意从大到小计算（保证是前行的意思）for(int j = sumN; j >= nums[i]; j--){// 启发自dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];（只与上一行的值有关）dp[j] = dp[j] || dp[j-nums[i]];}// （可能会加速）if(dp[sumN]) return true;}return dp[sumN];}
};