所有的LeetCode題解索引，可以看這篇文章——【算法和數(shù)據(jù)結(jié)構(gòu)】LeetCode題解。
一、題目
二、解法
??思路分析：本題可以抽象成一個01背包的問題，關(guān)于01背包可以看【算法與數(shù)據(jù)結(jié)構(gòu)】算法與數(shù)據(jù)結(jié)構(gòu)知識點。本題只需要求出數(shù)組的累積和，然后和的一半就可以視為背包的最大重量，目標(biāo)就是要判斷數(shù)組中是否有和為背包最大重量的子集。其中，物品重量和價值相同，就是數(shù)組元素的值。根據(jù)01背包的思想，我們寫出如下一維滾動數(shù)組的代碼。
??程序如下：
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for (int i : nums) sum += i; // 也可以用accumalte函數(shù)
if (sum % 2 != 0 || nums.size() < 2) return false;
vector<int> dp(sum/2 + 1, 0);
for (int i = 0; i < nums.size(); i++) {
for (int j = sum / 2; j >= nums[i]; j--) {
dp[j] = max(dp[j], dp[j - nums[i] ] + nums[i]);
}
}
if (dp[sum / 2] == sum / 2) return true;
return false;
}
};
復(fù)雜度分析：文章來源：http://www.zghlxwxcb.cn/news/detail-803066.html
- 時間復(fù)雜度： O ( n 2 ) O(n^2) O(n2)。
- 空間復(fù)雜度： O ( n ) O(n) O(n)。
三、完整代碼
# include <iostream>
# include <vector>
# include <numeric>
# include <algorithm>
using namespace std;
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for (int i : nums) sum += i; // 也可以用accumalte函數(shù)
if (sum % 2 != 0 || nums.size() < 2) return false;
vector<int> dp(sum/2 + 1, 0);
for (int i = 0; i < nums.size(); i++) {
for (int j = sum / 2; j >= nums[i]; j--) {
dp[j] = max(dp[j], dp[j - nums[i] ] + nums[i]);
}
}
if (dp[sum / 2] == sum / 2) return true;
return false;
}
};
int main() {
vector<int> nums = { 1,5,11,5 };
Solution s1;
bool result = s1.canPartition(nums);
cout << result << endl;
system("pause");
return 0;
}
end文章來源地址http://www.zghlxwxcb.cn/news/detail-803066.html
到了這里，關(guān)于【算法與數(shù)據(jù)結(jié)構(gòu)】416、LeetCode分割等和子集的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
