共计 2660 个字符，预计需要花费 7 分钟才能阅读完成。
读完本文，你能够去力扣拿下如下题目：
416. 宰割等和子集
———–
上篇文章 经典动静布局：0-1 背包问题 详解了通用的 0-1 背包问题，明天来看看背包问题的思维可能如何使用到其余算法题目。
而且，不是常常有读者问，怎么将二维动静布局压缩成一维动静布局吗？这就是状态压缩，很容易的，本文也会提及这种技巧。
一、问题剖析
先看一下题目：
算法的函数签名如下：
// 输出一个汇合，返回是否可能宰割成和相等的两个子集
bool canPartition(vector<int>& nums);对于这个问题，看起来和背包没有任何关系，为什么说它是背包问题呢？
首先回顾一下背包问题大抵的形容是什么：
给你一个可装载重量为 W 的背包和 N 个物品，每个物品有分量和价值两个属性。其中第 i 个物品的分量为 wt[i]，价值为 val[i]，当初让你用这个背包装物品，最多能装的价值是多少？
那么对于这个问题，咱们能够先对汇合求和，得出 sum，把问题转化为背包问题：
给一个可装载重量为 sum / 2 的背包和 N 个物品，每个物品的分量为 nums[i]。当初让你装物品，是否存在一种装法，可能恰好将背包装满？
你看，这就是背包问题的模型，甚至比咱们之前的经典背包问题还要简略一些，上面咱们就间接转换成背包问题，开始套前文讲过的背包问题框架即可。
PS：我认真写了 100 多篇原创，手把手刷 200 道力扣题目，全副公布在 labuladong 的算法小抄，继续更新 。倡议珍藏， 依照我的文章程序刷题，把握各种算法套路后投再入题海就蛟龙得水了。
二、解法剖析
第一步要明确两点，「状态」和「抉择」。
这个前文 经典动静布局：背包问题 曾经具体解释过了，状态就是「背包的容量」和「可抉择的物品」，抉择就是「装进背包」或者「不装进背包」。
第二步要明确 dp 数组的定义。
依照背包问题的套路，能够给出如下定义：
dp[i][j] = x 示意，对于前 i 个物品，以后背包的容量为 j 时，若 x 为 true，则阐明能够恰好将背包装满，若 x 为 false，则阐明不能恰好将背包装满。
比如说，如果 dp[4][9] = true，其含意为：对于容量为 9 的背包，若只是用前 4 个物品，能够有一种办法把背包恰好装满。
或者说对于本题，含意是对于给定的汇合中，若只对前 4 个数字进行抉择，存在一个子集的和能够恰好凑出 9。
依据这个定义，咱们想求的最终答案就是 dp[N][sum/2]，base case 就是 dp[..][0] = true 和 dp[0][..] = false，因为背包没有空间的时候，就相当于装满了，而当没有物品可抉择的时候，必定没方法装满背包。
第三步，依据「抉择」，思考状态转移的逻辑。
回忆方才的 dp 数组含意，能够依据「抉择」对 dp[i][j] 失去以下状态转移：
如果不把 nums[i] 算入子集，或者说你不把这第 i 个物品装入背包，那么是否可能恰好装满背包，取决于上一个状态 dp[i-1][j]，继承之前的后果。
如果把 nums[i] 算入子集，或者说你把这第 i 个物品装入了背包，那么是否可能恰好装满背包，取决于状态 dp[i-1][j-nums[i-1]]。
首先，因为 i 是从 1 开始的，而数组索引是从 0 开始的，所以第 i 个物品的分量应该是 nums[i-1]，这一点不要搞混。
dp[i - 1][j-nums[i-1]] 也很好了解：你如果装了第 i 个物品，就要看背包的残余分量 j - nums[i-1] 限度下是否可能被恰好装满。
换句话说，如果 j - nums[i-1] 的分量能够被恰好装满，那么只有把第 i 个物品装进去，也可恰好装满 j 的分量；否则的话，分量 j 必定是装不满的。
最初一步，把伪码翻译成代码，解决一些边界状况。
以下是我的 C++ 代码，齐全翻译了之前的思路，并解决了一些边界状况：
bool canPartition(vector<int>& nums) {
int sum = 0;
for (int num : nums) sum += num;
// 和为奇数时，不可能划分成两个和相等的汇合
if (sum % 2 != 0) return false;
int n = nums.size();
sum = sum / 2;
vector<vector<bool>>
dp(n + 1, vector<bool>(sum + 1, false));
// base case
for (int i = 0; i <= n; i++)
dp[i][0] = true;
for (int i = 1; i <= n; i++) {for (int j = 1; j <= sum; j++) {if (j - nums[i - 1] < 0) {
// 背包容量有余，不能装入第 i 个物品
dp[i][j] = dp[i - 1][j];
} else {
// 装入或不装入背包
dp[i][j] = dp[i - 1][j] || dp[i - 1][j-nums[i-1]];
}
}
}
return dp[n][sum];
}PS：我认真写了 100 多篇原创，手把手刷 200 道力扣题目，全副公布在 labuladong 的算法小抄，继续更新 。倡议珍藏， 依照我的文章程序刷题，把握各种算法套路后投再入题海就蛟龙得水了。
三、进行状态压缩
再进一步，是否能够优化这个代码呢？留神到 dp[i][j] 都是通过上一行 dp[i-1][..] 转移过去的，之前的数据都不会再应用了。
所以，咱们能够进行状态压缩，将二维 dp 数组压缩为一维，节约空间复杂度：
bool canPartition(vector<int>& nums) {int sum = 0, n = nums.size();
for (int num : nums) sum += num;
if (sum % 2 != 0) return false;
sum = sum / 2;
vector<bool> dp(sum + 1, false);
// base case
dp[0] = true;
for (int i = 0; i < n; i++)
for (int j = sum; j >= 0; j--)
if (j - nums[i] >= 0)
dp[j] = dp[j] || dp[j - nums[i]];
return dp[sum];
}这就是状态压缩，其实这段代码和之前的解法思路完全相同，只在一行 dp 数组上操作，i 每进行一轮迭代，dp[j] 其实就相当于 dp[i-1][j]，所以只须要一维数组就够用了。
惟一须要留神的是 j 应该从后往前反向遍历，因为每个物品（或者说数字）只能用一次，免得之前的后果影响其余的后果。
至此，子集切割的问题就齐全解决了，工夫复杂度 O(n\*sum)，空间复杂度 O(sum)。
_____________
我的 在线电子书 有 100 篇原创文章，手把手带刷 200 道力扣题目，倡议珍藏！对应的 GitHub 算法仓库 曾经取得了 70k star，欢送标星！
