LeetCode Partition Equal Subset Sum Given a non-empty array 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. Note:

1. Each of the array element will not exceed 100.
2. The array size will not exceed 200.

Example 1:

Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

---

问一个数组能否划分成两个子数组，且这两个子数组的和相等。 如果成立，首先必须满足数组的和是偶数，然后必须能找到一个子数组的和是总和的一半。所以问题转换为从数组中取若干个元素，使得取出元素之和为target（原数组和的一半）。 用动态规划求解，令dp[j]表示能抽取一个子数组之和为j的子数组。递推式为： if dp[j] then dp[nums[i]+j]=true 含义为如果能得到子数组和为j的子数组，那么再取一个元素nums[i]扔到子数组中，就能得到子数组和为j+nums[i]的子数组。所以对于数组中的每个元素nums[i]，遍历dp[0,…,target-nums[i]]应用上式。 有一点需要注意的是，遍历dp时，必须从大到小遍历，否则会出错。比如数组[1,2,5]，dp[0]=1，对于元素1，如果我们从小到大遍历dp，则dp[0,…,3]都等于true；对于元素2，则会导致dp[2+2]=true。但是如果从大到小遍历dp，即dp[3,…,0]，则对于元素1，只会设置dp[1]=true，最终不会导致dp[4]=true。 完整代码如下： [cpp] class Solution { public: bool canPartition(vector<int>& nums) { int sum = accumulate(nums.begin(), nums.end(), 0); if (sum & 1)return false; int target = sum / 2; vector<int> dp(target + 1); dp[0] = 1; for (int i = 0; i < nums.size(); ++i) { for (int j = target – nums[i]; j >= 0; –j) { if (dp[j])dp[j + nums[i]] = 1; } } return dp[target]; } }; [/cpp] 本代码提交AC，用时39MS。]]>