1. 题⽬链接：416. 分割等和⼦集
2. 题⽬描述:
3. 解法（动态规划）：
算法思路：
先将问题转化成我们「熟悉」的题型。 如果数组能够被分成两个相同元素之和相同的⼦集，那么原数组必须有下⾯⼏个性质：
i. 所有元素之和应该是⼀个偶数；
ii. 数组中最⼤的元素应该⼩于所有元素总和的⼀半；
iii. 挑选⼀些数，这些数的总和应该等于数组总和的⼀半。 根据前两个性质，我们可以提前判断数组能够被划分。
根据最后⼀个性质，我们发现问题就转化成 了「01 背包」的模型：
i. 数组中的元素只能选择⼀次；
ii. 每个元素⾯临被选择或者不被选择的处境；
iii. 选出来的元素总和要等于所有元素总和的⼀半。 其中，数组内的元素就是物品，总和就是背包。 那么我们就可以⽤背包模型的分析⽅式，来处理这道题。
请⼤家注意，「不要背」状态转移⽅程，因为题型变化之后，状态转移⽅程就会跟着变化。我们要 记住的是分析问题的模式。⽤这种分析问题的模式来解决问题。
1. 状态表⽰：
dp[i][j] 表⽰在前 i 个元素中选择，所有的选法中，能否凑成总和为 j 这个数。
2. 状态转移⽅程：
⽼规矩，根据「最后⼀个位置」的元素，结合题⽬的要求，分情况讨论：
i. 不选择 nums[i] ：那么我们是否能够凑成总和为 j ，就要看在前 i - 1 个元素中 选，能否凑成总和为 j 。根据状态表⽰，此时 dp[i][j] = dp[i - 1][j] ；
ii. 选择 nums[i] ：这种情况下是有前提条件的，此时的 nums[i] 应该是⼩于等于 j 。 因为如果这个元素都⽐要凑成的总和⼤，选择它就没有意义呀。那么我们是否能够凑成总和 为 j ，就要看在前 i - 1 个元素中选，能否凑成总和为 j - nums[i] 。根据状态表 ⽰，此时 dp[i][j] = dp[i - 1][j - nums[i]] 。
综上所述，两种情况下只要有⼀种能够凑成总和为 j ，那么这个状态就是 true 。
因此，状态转 移⽅程为： dp[i][j] = dp[i - 1][j] if(nums[i - 1] <= j) dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i]]
3. 初始化：
由于需要⽤到上⼀⾏的数据，因此我们可以先把第⼀⾏初始化。 第⼀⾏表⽰不选择任何元素，要凑成⽬标和 j 。只有当⽬标和为 0 的时候才能做到，因此第⼀ ⾏仅需初始化第⼀个元素 dp[0][0] = true
4. 填表顺序：
根据「状态转移⽅程」，我们需要「从上往下」填写每⼀⾏，每⼀⾏的顺序是「⽆所谓的」。
5. 返回值：
根据「状态表⽰」，返回 dp[n][aim] 的值。 其中 n 表⽰数组的⼤⼩， aim 表⽰要凑的⽬标和。
6. 空间优化：
所有的「背包问题」，都可以进⾏空间上的优化。 对于 01背包类型的，我们的优化策略是：
i. 删掉第⼀维；
ii. 修改第⼆层循环的遍历顺序即可。
C++ 优化前的算法代码：
class Solution
{
public:
bool canPartition(vector<int>& nums)
{
//求和
int sum=0;
for(int i=0;i<nums.size();i++)
{
sum+=nums[i];
}
//判断奇偶数，若是为奇数不可能分为两类，直接返回false
if(sum%2==1)
{
return false;
}
//建表
int m=nums.size();
int n=sum/2;
vector<vector<int>>dp(m+1,vector<int>(n+1));
//初始化
dp[0][0]=true;
for(int i=1;i<=m;i++)
{
dp[i][0]=true;
}
//填表
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
//不选
dp[i][j]=dp[i-1][j];
//选
if(j-nums[i-1]>=0)
{
dp[i][j]=(dp[i-1][j]||dp[i-1][j-nums[i-1]]);
}
}
}
//返回值
return dp[m][n];
}
};C++ 空间优化后的算法代码：
class Solution
{
public:
bool canPartition(vector<int>& nums)
{
//求和
int sum=0;
for(int i=0;i<nums.size();i++)
{
sum+=nums[i];
}
//判断奇偶数，若是为奇数不可能分为两类，直接返回false
if(sum%2==1)
{
return false;
}
//建表
int m=nums.size();
int n=sum/2;
vector<int>dp(n+1);
//初始化
dp[0]=true;
//填表
for(int i=1;i<=m;i++)
{
for(int j=n;j>=1;j--)
{
if(j-nums[i-1]>=0)
{
dp[j]=(dp[j]||dp[j-nums[i-1]]);
}
}
}
//返回值
return dp[n];
}
};Java 优化前算法代码：
class Solution
{
public boolean canPartition(int[] nums)
{
int n = nums.length, sum = 0;
for(int x : nums) sum += x;
if(sum % 2 == 1) return false; // 如果不能平分，直接返回 false
int aim = sum / 2;
boolean[][] dp = new boolean[n + 1][aim + 1]; // 建表
for(int i = 0; i <= n; i++) dp[i][0] = true; // 初始化
for(int i = 1; i <= n; i++) // 填表
for(int j = 1; j <= aim; 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[n][aim];
}
}
Java 空间优化后的算法代码：
class Solution
{
public boolean canPartition(int[] nums)
{
int n = nums.length, sum = 0;
for(int x : nums) sum += x;
if(sum % 2 == 1) return false; // 如果不能平分，直接返回 false
int aim = sum / 2;
boolean[] dp = new boolean[aim + 1]; // 建表
dp[0] = true; // 初始化
for(int i = 1; i <= n; i++) // 填表
for(int j = aim; j >= nums[i - 1]; j--) // ?定要注意修改遍历顺序
dp[j] = dp[j] || dp[j - nums[i - 1]];
return dp[aim];
}
}