今天又是刷leetcode的一天呀，开局不顺，今天做的第二道题就不会了，看了别人的回答才会的，记录一下。
这道题是 416. Partition Equal Subset Sum
就是能否将一个数组分成两个不相交的子集，使得两个子集之和相等。
一开始我想的是首先判断数组之和是不是偶数，不是的话直接return false。然后再使用dfs寻找原数组中是否存在某个子集之和是原数组所有元素之和的一半，代码如下：
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if(sum % 2 != 0) return false;
return helper(nums, sum/2, 0, 0);//TLE
}
bool helper(vector<int>& nums, int target, int start, int sum){
if(sum == target) return true;
for(int i = start; i < nums.size(); i++){
if(helper(nums, target, i+1, sum+nums[i])) return true;
}
return false;
}
};
很明显，这种做法在nums数组中元素个数稍多的情况下就会超时，因为一个含有n个元素的数组的子集个数是 2n 个，这个复杂度是显而易见的高。
于是我们需要使用dp去做。
在网上搜了一下别人的讲解，这道题本质上是01背包问题，01背包问题是经典的dp问题，我们先简单回顾一下01背包问题：
0-1 背包问题：
给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是 wi，其价值为 vi。
问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？
01背包问题的状态转移方程为：
if(j >= w[i])
m[i][j] = max(m[i-1][j], m[i-1][j-w[i]] + v[i]);
else
m[i][j] = m[i-1][j];
简单解释一下，
m[i][j] 表示可选物品为 第1到第i件 物品，且背包容量为 j 时所能获得的最大价值
- 如果当前背包容量能装下目前的第i个物品，那么m[i][j] = max(m[i-1][j], m[i-1][j-w[i]] + v[i])。其中m[i-1][j]表示不装第i个物品，m[i-1][j-w[i]] + v[i]表示装第i个物品
- 如果当前背包容量不能装下目前的第i个物品，那么相当于目前第i个物品不在考虑范围内（因为光装它一个都装不下），这种情况下m[i][j]自然就等于m[i-1][j]
回到我们这道题，其实我们也可以按照这种逻辑定义原问题的子问题：
dp[i][j]表示可选数字为nums数组中第0个到第i(0 <= i < nums.size())个数字的时候，是否可以找到其中一个子集，使得子集各元素之和等于j(0 <= j <= sum/2, sum表示nums各元素之和)。
根据这个定义，我们可以写出如下代码：
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if(sum % 2 != 0) return false;
vector<vector<bool>> dp(nums.size(), vector<bool>(sum/2+1, false));
//dp[i][j]表示可选数字为nums数组中第0到第i个数字的时候，是否可以凑出来和为j的子集
//其中0<= i <= nums.size()-1, 0 <= j <= sum/2
for(int i = 0; i < nums.size(); i++) dp[i][0] = true;
for(int i = 1; i <= sum/2; i++) dp[0][i] = nums[0]==i;
for(int i = 1; i < nums.size(); i++){
for(int j = 1; j <= sum/2; j++){
if(j >= nums[i]) dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]];
else dp[i][j] = dp[i-1][j];
}
}
return dp[nums.size()-1][sum/2];
}
};
其中下面代码是边界条件的初始化
for(int i = 0; i < nums.size(); i++) dp[i][0] = true;//子集之和为0，相当于不选择任何元素
for(int i = 1; i <= sum/2; i++) dp[0][i] = nums[0]==i;//可选数字只有第一个数字，直接判断该数字是不是j
可以看到，每个状态值只依赖于上一行的状态值，所以事实上可以在空间上进行优化，不过时间上应该不能优化了。