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
动态规划
一维数组
该代码是解决力扣题目416《分割等和子集》的解法之一。它基于动态规划的思想，尝试找出是否存在一个子集，其元素之和等于整个数组元素和的一半。下面对这段代码逐行进行详细注释：
class Solution {
public:
// canPartition函数尝试判断nums数组是否可以被分割成两个和相等的子集。
bool canPartition(vector<int>& nums) {
// sum用来存储nums数组中所有元素的和。
int sum=0;
// 遍历nums数组，计算总和。
for(int i=0;i<nums.size();i++)
sum+=nums[i];
// 如果总和是奇数，直接返回false，因为奇数不可能被分割成两个和相等的部分。
if(sum%2==1) return false;
// 计算目标值tar，即我们希望找到的子集的和，应该是总和的一半。
int tar=sum/2;
vector<int> dp(tar+1,0);
// 开始动态规划过程。
for(int i=0;i<nums.size();i++)
{
// 从tar向下遍历至nums[i]，这里的意思是尝试将当前元素nums[i]加入到子集中。
for(int j=tar;j>=nums[i];j--)
{
// 对于每个j，我们尝试更新dp[j]。
// dp[j]是在考虑当前元素nums[i]的情况下，能够达到的最大和。
// 我们比较不加入当前元素的和dp[j]与加入当前元素后的和dp[j-nums[i]]+nums[i]，取两者的较大值。
dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
}
}
// 如果dp[tar]等于tar，意味着我们确实找到了一个子集，它的和为总和的一半，返回true。
if(dp[tar]==tar) return true;
// 否则，没有找到这样的子集，返回false。
return false;
}
};
这段代码的核心思想是使用一维动态规划来保存子集和的可能性。dp[j]存储的是在考虑到当前元素之前，能够构成的子集和为j时，这个子集中元素的最大总和。这个解法很巧妙地利用了动态规划的特性来避免直接枚举所有可能的子集，从而大大提高了算法的效率。
二维数组（
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0; // 用于累加数组中所有元素的和
// 遍历数组以计算总和
for (int i = 0; i < nums.size(); i++)
sum += nums[i];
// 如果总和是奇数，则无法平分，直接返回false
if (sum % 2 == 1) return false;
// 计算目标和，即每个子集的和
int tar = sum / 2;
// 初始化动态规划表，大小为210x(target+1)，210是根据题目给出的最大数组长度大小+10来预留的空间
vector<vector<int>> dp(210, vector<int>(tar + 1, 0));
// 初始化第一行，这里假设第一个元素选取，更新所有能达到的和为nums[0]
for (int j = nums[0]; j <= tar; j++)
dp[0][j] = nums[0];
// 遍历数组中的每个元素，除了第一个
for (int i = 1; i < nums.size(); i++) {
// 遍历所有可能的子集和
for (int j = 0; j <= tar; j++) {
// 当前和小于当前元素值，不能选取当前元素，子集和保持不变
if (j < nums[i])
dp[i][j] = dp[i - 1][j];
// 否则，可以选择不包含当前元素，或者包含当前元素，取两者可能性中较大的值
else
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
}
}
// 检查最后一个元素对应的目标子集和是否达到了目标值，如果是则表示可以分割
if (dp[nums.size() - 1][tar] == tar) return true;
// 否则无法分割成和相等的子集
return false;
}
};
易错：在力扣上我定义了全局变量dp（因为一开始我使用的是数组，需要开比较大的空间，得定义在全局变量中，，因为力扣提前执行的时候是不会重复加载全局变量的 只会加载一次 之后每次运行新的测试用例只会执行那个功能函数，如需使用，需要每次在函数中使用memset函数对数组初始化为0。