LeetCode416：分割等和子集

题目描述
给你一个只包含正整数的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

在这里插入图片描述
解题思想

    [1,5,11,5]   和为22，其中一半为 11。如果能寻找到若干数的和为11则成立可以抽象为一个0-1背包问题：容量为11的背包能否被装满上述的数组可以看作 重量和价值等同dp[j]：容量为j的背包最大价值dp[j]递推公式：dp[j] = max(dp[j], dp[j-weight[i]] + value[i])本题：dp[j] = max(dp[j],dp[j-nums[i]]+nums[i])遍历顺序：for (int i = 0; i < n; i++)//背包倒序遍历for (int j = target; j >= nums[i]; j--) {dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);}

代码

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