416. 分割等和子集
題目難易：中等
給定一個(gè)只包含正整數(shù)的非空數(shù)組。是否可以將這個(gè)數(shù)組分割成兩個(gè)子集，使得兩個(gè)子集的元素和相等。
注意: 每個(gè)數(shù)組中的元素不會(huì)超過(guò) 100 數(shù)組的大小不會(huì)超過(guò) 200
示例 1:
輸入: [1, 5, 11, 5]
輸出: true
解釋: 數(shù)組可以分割成 [1, 5, 5] 和 [11].
示例 2:
輸入: [1, 2, 3, 5]
輸出: false
解釋: 數(shù)組不能分割成兩個(gè)元素和相等的子集.
提示：
1 <= nums.length <= 200
1 <= nums[i] <= 100
思路
這道題目初步看，和如下兩題幾乎是一樣的，大家可以用回溯法，解決如下兩題
- 698.劃分為k個(gè)相等的子集
- 473.火柴拼正方形
這道題目是要找是否可以將這個(gè)數(shù)組分割成兩個(gè)子集，使得兩個(gè)子集的元素和相等。
那么只要找到集合里能夠出現(xiàn) sum / 2 的子集總和，就算是可以分割成兩個(gè)相同元素和子集了。
本題是可以用回溯暴力搜索出所有答案的，但最后超時(shí)了，也不想再優(yōu)化了，放棄回溯，直接上01背包吧。
如果對(duì)01背包不夠了解，建議仔細(xì)看完如下兩篇：
動(dòng)態(tài)規(guī)劃：關(guān)于01背包問(wèn)題，你該了解這些！(opens new window)
動(dòng)態(tài)規(guī)劃：關(guān)于01背包問(wèn)題，你該了解這些?。L動(dòng)數(shù)組）(opens new window)
#01背包問(wèn)題
背包問(wèn)題，大家都知道，有N件物品和一個(gè)最多能背重量為W 的背包。第i件物品的重量是weight[i]，得到的價(jià)值是value[i] 。每件物品只能用一次，求解將哪些物品裝入背包里物品價(jià)值總和最大。
背包問(wèn)題有多種背包方式，常見(jiàn)的有：01背包、完全背包、多重背包、分組背包和混合背包等等。
要注意題目描述中商品是不是可以重復(fù)放入。
即一個(gè)商品如果可以重復(fù)多次放入是完全背包，而只能放入一次是01背包，寫(xiě)法還是不一樣的。
要明確本題中我們要使用的是01背包，因?yàn)樵匚覀冎荒苡靡淮巍?/p>
回歸主題：首先，本題要求集合里能否出現(xiàn)總和為 sum / 2 的子集。
那么來(lái)一一對(duì)應(yīng)一下本題，看看背包問(wèn)題如何來(lái)解決。
只有確定了如下四點(diǎn)，才能把01背包問(wèn)題套到本題上來(lái)。
背包的體積為sum / 2
背包要放入的商品（集合里的元素）重量為 元素的數(shù)值，價(jià)值也為元素的數(shù)值
背包如果正好裝滿(mǎn)，說(shuō)明找到了總和為 sum / 2 的子集。
背包中每一個(gè)元素是不可重復(fù)放入。
以上分析完，我們就可以套用01背包，來(lái)解決這個(gè)問(wèn)題了。
動(dòng)規(guī)五部曲分析如下：
確定dp數(shù)組以及下標(biāo)的含義
01背包中，dp[j] 表示： 容量為j的背包，所背的物品價(jià)值最大可以為dp[j]。
本題中每一個(gè)元素的數(shù)值既是重量，也是價(jià)值。
套到本題，dp[j]表示 背包總?cè)萘浚ㄋ苎b的總重量）是j，放進(jìn)物品后，背的最大重量為dp[j]。
那么如果背包容量為target， dp[target]就是裝滿(mǎn) 背包之后的重量，所以 當(dāng) dp[target] == target 的時(shí)候，背包就裝滿(mǎn)了。
有錄友可能想，那還有裝不滿(mǎn)的時(shí)候？
拿輸入數(shù)組 [1, 5, 11, 5]，舉例， dp[7] 只能等于 6，因?yàn)?只能放進(jìn) 1 和 5。
而dp[6] 就可以等于6了，放進(jìn)1 和 5，那么dp[6] == 6，說(shuō)明背包裝滿(mǎn)了。
確定遞推公式
01背包的遞推公式為：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
本題，相當(dāng)于背包里放入數(shù)值，那么物品i的重量是nums[i]，其價(jià)值也是nums[i]。
所以遞推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
dp數(shù)組如何初始化
在01背包，一維dp如何初始化，已經(jīng)講過(guò)，
從dp[j]的定義來(lái)看，首先dp[0]一定是0。
如果題目給的價(jià)值都是正整數(shù)那么非0下標(biāo)都初始化為0就可以了，如果題目給的價(jià)值有負(fù)數(shù)，那么非0下標(biāo)就要初始化為負(fù)無(wú)窮。
這樣才能讓dp數(shù)組在遞推的過(guò)程中取得最大的價(jià)值，而不是被初始值覆蓋了。
本題題目中 只包含正整數(shù)的非空數(shù)組，所以非0下標(biāo)的元素初始化為0就可以了。
代碼如下：
// 題目中說(shuō)：每個(gè)數(shù)組中的元素不會(huì)超過(guò) 100，數(shù)組的大小不會(huì)超過(guò) 200
// 總和不會(huì)大于20000，背包最大只需要其中一半，所以10001大小就可以了
vector dp(10001, 0);
確定遍歷順序
在動(dòng)態(tài)規(guī)劃：關(guān)于01背包問(wèn)題，你該了解這些?。L動(dòng)數(shù)組） (opens new window)中就已經(jīng)說(shuō)明：如果使用一維dp數(shù)組，物品遍歷的for循環(huán)放在外層，遍歷背包的for循環(huán)放在內(nèi)層，且內(nèi)層for循環(huán)倒序遍歷！
代碼如下：
// 開(kāi)始 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]);
}
}
舉例推導(dǎo)dp數(shù)組
dp[j]的數(shù)值一定是小于等于j的。
如果dp[j] == j 說(shuō)明，集合中的子集總和正好可以湊成總和j，理解這一點(diǎn)很重要。
用例1，輸入[1,5,11,5] 為例，如圖：
最后dp[11] == 11，說(shuō)明可以將這個(gè)數(shù)組分割成兩個(gè)子集，使得兩個(gè)子集的元素和相等。
綜上分析完畢，C++代碼如下：
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
// dp[i]中的i表示背包內(nèi)總和
// 題目中說(shuō)：每個(gè)數(shù)組中的元素不會(huì)超過(guò) 100，數(shù)組的大小不會(huì)超過(guò) 200
// 總和不會(huì)大于20000，背包最大只需要其中一半，所以10001大小就可以了
vector<int> dp(10001, 0);
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
}
// 也可以使用庫(kù)函數(shù)一步求和
// int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum % 2 == 1) return false;
int target = sum / 2;
// 開(kāi)始 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]);
}
}
// 集合中的元素正好可以湊成總和target
if (dp[target] == target) return true;
return false;
}
};
python
class Solution:
def canPartition(self, nums: List[int]) -> bool:
_sum = 0
# dp[i]中的i表示背包內(nèi)總和
# 題目中說(shuō)：每個(gè)數(shù)組中的元素不會(huì)超過(guò) 100，數(shù)組的大小不會(huì)超過(guò) 200
# 總和不會(huì)大于20000，背包最大只需要其中一半，所以10001大小就可以了
dp = [0] * 10001
for num in nums:
_sum += num
# 也可以使用內(nèi)置函數(shù)一步求和
# _sum = sum(nums)
if _sum % 2 == 1:
return False
target = _sum // 2
# 開(kāi)始 0-1背包
for num in nums:
for j in range(target, num - 1, -1): # 每一個(gè)元素一定是不可重復(fù)放入，所以從大到小遍歷
dp[j] = max(dp[j], dp[j - num] + num)
# 集合中的元素正好可以湊成總和target
if dp[target] == target:
return True
return False
(簡(jiǎn)化版)
class Solution:
def canPartition(self, nums: List[int]) -> bool:
if sum(nums) % 2 != 0:
return False
target = sum(nums) // 2
dp = [0] * (target + 1)
for num in nums:
for j in range(target, num-1, -1):
dp[j] = max(dp[j], dp[j-num] + num)
return dp[-1] == target
二維DP版文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-785254.html
class Solution:
def canPartition(self, nums: List[int]) -> bool:
total_sum = sum(nums)
if total_sum % 2 != 0:
return False
target_sum = total_sum // 2
dp = [[False] * (target_sum + 1) for _ in range(len(nums) + 1)]
# 初始化第一行（空子集可以得到和為0）
for i in range(len(nums) + 1):
dp[i][0] = True
for i in range(1, len(nums) + 1):
for j in range(1, target_sum + 1):
if j < nums[i - 1]:
# 當(dāng)前數(shù)字大于目標(biāo)和時(shí)，無(wú)法使用該數(shù)字
dp[i][j] = dp[i - 1][j]
else:
# 當(dāng)前數(shù)字小于等于目標(biāo)和時(shí)，可以選擇使用或不使用該數(shù)字
dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]
return dp[len(nums)][target_sum]
一維DP版文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-785254.html
class Solution:
def canPartition(self, nums: List[int]) -> bool:
total_sum = sum(nums)
if total_sum % 2 != 0:
return False
target_sum = total_sum // 2
dp = [False] * (target_sum + 1)
dp[0] = True
for num in nums:
# 從target_sum逆序迭代到num，步長(zhǎng)為-1
for i in range(target_sum, num - 1, -1):
dp[i] = dp[i] or dp[i - num]
return dp[target_sum]
到了這里，關(guān)于動(dòng)態(tài)規(guī)劃（分割等和子集）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
