题目描述
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:
Each of the array element will not exceed 100.
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.
解题思路
要将数组分为两个和相等的子数组，首先需要这个数组的和必须为2的倍数。如果数组所有元素之和不是2的倍数，则一定不能分为两个子数组，直接返回false。
如果可以被2整除，那么我们就可以将它变成一个一维的背包问题。假设这个背包的容量为这个数组的所有元素和的一半，物品的花费和它的价值都是数组的元素值。然后利用背包问题的解法，进行两重的迭代。对于第i个物品，我们花费v的价格可以得到的价值为dp[i][v]。由于物品的花费和价值相同，因此，只有将背包的所有容量用光时，才有可能拿到价值为数组和一半的物品；同时也意味着，在这个背包容量下，我们拿到的最大价值也只能是数组和的一半。
因此，只需要按照普通的背包问题，需要算出购买第i个物品，花费总价格v时的最大值即可。最后，如果花费的价格为元素和的一半，而且得到的价值为元素和的一半，那么就可以认为，这个数组能被分为两个元素和相等的子数组。状态转移方程：
f(i)(v)代表花费总价格v，是否买下第i个物品时候获得的总价值。
c(i)代表第i件物品的代价
f(i)(v) = max(f(i-1)(v), f(i-1)(v-c(i))+c(i)), v >= c(i)
关于遍历的顺序，由上面的状态转移方程可以看到，在计算f(i)(v)之前我们需要知道f(i-1)(v-c(i))和f(i-1)(v)的值，也就是上一次迭代花费v和v-c(i)时获得的总收益。因此，我们只需要按照物品0-N的顺序循环即可（N代表问题给出的数组的长度）。
当然，作为一维背包问题，我们可以对它进行一定的优化，将dp数组从2维下降到1维。对于第i次迭代，花费v而言，它关注的是前一次迭代i-1中，花费v或者v-c(i)获得的价值，因此只要更新它的值即可，不需要保存值。最后找dp[N][V]的值是否等于和的一半即可。
但注意循环顺序需要改变，内循环需要从V到c(i)循环。因为后面的值依赖于前面的值作更新，不能让前面的值先作更新操作。
时间复杂度
计算数组和O(N)。动态规划O(N*V).
空间复杂度
经过状态压缩之后，动归数组O(V)
源码
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sums = 0;
for (int i = 0; i < nums.size(); ++i) {
sums += nums[i];
}
if (sums % 2 != 0) {
return false;
}
int V = sums / 2;
int dp[V + 1] = {0};
for (int i = 0; i < nums.size(); ++i) {
for (int j = V; j >= nums[i]; --j) {
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
return dp[V] == V ? true : false;
}
};
