題目來源：https://leetcode.cn/problems/partition-equal-subset-sum/description/

C++題解（思路來源代碼隨想錄） ：

背包問題有多種背包方式，常見的有：01背包、完全背包、多重背包、分組背包和混合背包等等。一個(gè)商品如果可以重復(fù)多次放入是完全背包，而只能放入一次是01背包，本題中是01背包。

把01背包問題套到本題上來。

• 背包的體積為sum / 2
• 背包要放入的商品（集合里的元素）重量為元素的數(shù)值，價(jià)值也為元素的數(shù)值
• 背包如果正好裝滿，說明找到了總和為 sum / 2 的子集。
• 背包中每一個(gè)元素是不可重復(fù)放入。

以上分析完，我們就可以套用01背包，來解決這個(gè)問題了。

1. 確定dp數(shù)組以及下標(biāo)的含義。二維數(shù)組: dp[i][j]表示從下標(biāo)為[0-i]的物品里任意取，放進(jìn)容量為j的背包，價(jià)值總和最大是多少。
2. 確定遞推公式。兩種情況：不放物品i：由dp[i - 1][j]推出，即背包容量為j，里面不放物品i的最大價(jià)值，此時(shí)dp[i][j]就是dp[i - 1][j]。(其實(shí)就是當(dāng)物品i的重量大于背包j的重量時(shí)，物品i無法放進(jìn)背包中，所以背包內(nèi)的價(jià)值依然和前面相同。)；放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 為背包容量為j - weight[i]的時(shí)候不放物品i的最大價(jià)值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的價(jià)值），就是背包放物品i得到的最大價(jià)值。所以遞歸公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])。
3. dp數(shù)組初始化。一定要和dp數(shù)組的定義吻合，否則到遞推公式的時(shí)候就會(huì)越來越亂。首先從dp[i][j]的定義出發(fā)，如果背包容量j為0的話，即dp[i][0]，無論是選取哪些物品，背包價(jià)值總和一定為0。狀態(tài)轉(zhuǎn)移方程可以看出i 是由 i-1 推導(dǎo)出來，那么i為0的時(shí)候就一定要初始化，即i為0，存放編號(hào)0的物品的時(shí)候，各個(gè)容量的背包所能存放的最大價(jià)值。當(dāng) j < weight[0]的時(shí)候，dp[0][j] 應(yīng)該是 0；當(dāng)j >= weight[0]時(shí)，dp[0][j] 應(yīng)該是value[0]。
4. 確定遍歷順序。有兩個(gè)遍歷的維度：物品與背包重量。都可以！ 但是先遍歷物品更好理解。
5. 舉例推導(dǎo)dp數(shù)組。

class Solution {
public:bool canPartition(vector<int>& nums) {int len = nums.size();int sum = 0;for(int i = 0; i < len; i++) {sum += nums[i];}if(sum % 2 == 1) return false;vector<vector<int>> dp(len, vector<int>(sum/2+1, 0));for(int ii = nums[0]; ii <= sum/2; ii++) {dp[0][ii] = nums[0];}// 相當(dāng)于包容量為sum/2，在len個(gè)物品中挑選，能裝滿則返回true。// 表示從0-j的元素中，取出和小于k的最大值。for(int j = 1; j < len; j++) {for(int k = 0; k <= sum/2; k++) {if(k < nums[j]) dp[j][k] = dp[j-1][k];else dp[j][k] = max(dp[j-1][k], dp[j-1][k-nums[j]]+nums[j]);}}if(dp[len-1][sum/2] == sum/2) return true;else return false;}
};

# 使用一維dp數(shù)組（滾動(dòng)數(shù)組）

在使用二維數(shù)組的時(shí)候，遞推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

其實(shí)可以發(fā)現(xiàn)如果把dp[i - 1]那一層拷貝到dp[i]上，表達(dá)式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);

與其把dp[i - 1]這一層拷貝到dp[i]上，不如只用一個(gè)一維數(shù)組了，只用dp[j]（一維數(shù)組，也可以理解是一個(gè)滾動(dòng)數(shù)組）。這就是滾動(dòng)數(shù)組的由來，需要滿足的條件是上一層可以重復(fù)利用，直接拷貝到當(dāng)前層。

在一維dp數(shù)組中，dp[j]表示：容量為j的背包，所背的物品價(jià)值可以最大為dp[j]。

注意：遍歷順序必須先遍歷物品再遍歷包容量，且更新內(nèi)層for循環(huán)需要遞減（從后往前），因?yàn)闈L動(dòng)數(shù)組的更新需要用到未更新的前面元素，如果是遞增（從前往后），前面更新的元素會(huì)影響后面的元素。

class Solution {
public:bool canPartition(vector<int>& nums) {int sum = 0;// dp[i]中的i表示背包內(nèi)總和// 題目中說：每個(gè)數(shù)組中的元素不會(huì)超過 100，數(shù)組的大小不會(huì)超過 200// 總和不會(huì)大于20000，背包最大只需要其中一半，所以10001大小就可以了vector<int> dp(10001, 0);for (int i = 0; i < nums.size(); i++) {sum += nums[i];}// 也可以使用庫函數(shù)一步求和// int sum = accumulate(nums.begin(), nums.end(), 0);if (sum % 2 == 1) return false;int target = sum / 2;// 開始 01背包for(int i = 0; i < nums.size(); i++) {for(int j = target; j >= nums[i]; j--) { // 每一個(gè)元素一定是不可重復(fù)放入，所以從大到小遍歷dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);}}// 集合中的元素正好可以湊成總和targetif (dp[target] == target) return true;return false;}
};