今天和大家聊的问题叫做 分割等和子集，我们先来看题面：https://leetcode-cn.com/problems/partition-equal-subset-sum/
Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例
示例 1： 输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。 示例 2： 输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。
解题
基本思路：当数组能分成两个相等的子数组时，必定是偶数，且其值必定为总和的一半，令其为target，此时，问题转换成在数组中求和为target的子数组，一个很明显的动态规划问题。
class Solution { public: bool canPartition(vector<int>& nums) { int sum = accumulate(nums.begin(), nums.end(), 0); if(sum & 1) return false; int target = sum >> 1; int size = nums.size(); bool dp[size+1][target+1]; memset(dp, 0, sizeof(bool)*(size+1)*(target+1)); for(int i=0; i<=size; ++i) dp[i][0] = 1; for(int i=1; i<size+1; ++i) { for(int j=0; j<target+1; ++j) { dp[i][j] = dp[i-1][j]; if (j >= nums[i-1]) dp[i][j] = dp[i][j] || dp[i-1][j-nums[i-1]]; } } return dp[size][target]; } };
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
