LeetCode416：分割等和子集

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

代码如下：

class Solution {
public:bool canPartition(vector<int>& nums) {int m = nums.size();vector<int> dp(10010, 0);int sum = 0;for(int i = 0; i < m; i++){sum += nums[i];}if(sum % 2 == 1)    return false;int target = sum / 2;for(int i = 0; i < m; i++){for(int j = target; j >= nums[i]; j--){dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);}}if(dp[target] == target)    return true;return false;}
};

代码讲解：这个题目首先我们要明白一件事情，就是要把这个分成一个相等的子集，那么其实我们就可以看似为一个01背包问题，怎么去转化为这个01背包，就是我们先把所有的子集加起来除以2，就是背包大小，看看里面的子集能不能刚刚好填满这个背包，要是能的话，返回true，否则返回false，这个里面要注意的是，if（sum % 2 == 1）return false;这个原因是因为要是奇数的话，有小数点，你放进去的东西不能够是半个吧，因为题目都给你的全是整形数据。