分割等和子集
题目
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100 数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
思路
从题目可以看出，对于每个数要么选要么不选。典型的背包问题。再看 ( 注意： ) 元素的和最大值是 100 * 200 =20000 ，值不是很大。那么直接动态规划解决。
#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;
bool canPartition(vector<int>& nums) {
int sum = 0;
for (int i = 0; i < nums.size(); i++)
{
sum += nums[i];
}
if (sum%2)
{
return false;
}
int n = nums.size();
int C = sum / 2;
vector<bool> memo((__int64)C+1,false);
for (int i = 0; i <= C; i++)
{
memo[i] = (nums[0] == i);
}
for (int i = 1; i < n; i++)
{
for (int j = C; j >= nums[i]; j--) {
memo[j] = memo[j] || memo[(__int64)j - nums[i]];
}
}
return memo[C];
}
int main()
{
//int arr[] = { 17,58,41,75,61,70,52,7,38,11,40,58,44,45,4,81,67,54,79,80,15,3,14,16,9,66,69,41,72,37,28,3,33,90,56,12,72,49,35,22,49,27,49,82,41,77,100,82,18,95,24,51,37,2,34,82,70,53,73,32,90,98,81,22,73,76,79,40,27,62,45,96,36,15,63,28,54,88,63,37,58,9,62,98,93,72,99,53,91,29,61,31,11,42,20,35,50,68,10,86 };
int arr[] = { 1, 5, 11, 5 };
vector<int> nums(arr, arr + 4);
bool flag = canPartition(nums);
nums.clear();
cout << flag <<endl;
}
优化
由于本题的特殊性，只需要知道有相加满足总和的一半就可以提前结束了;
所以进行优化，在满足条件的时候直接返回True
#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;
bool canPartition(vector<int>& nums) {
int sum = 0;
for (int i = 0; i < nums.size(); i++)
{
sum += nums[i];
}
if (sum%2)
{
return false;
}
int n = nums.size();
int C = sum / 2;
vector<bool> memo((__int64)C+1,false);
for (int i = 0; i <= C; i++)
{
memo[i] = (nums[0] == i);
}
for (int i = 1; i < n; i++)
{
if (memo[C]) return memo[C]; // 提前结束
for (int j = C; j >= nums[i]; j--) {
memo[j] = memo[j] || memo[(__int64)j - nums[i]];
}
}
return memo[C];
}
int main()
{
//int arr[] = { 17,58,41,75,61,70,52,7,38,11,40,58,44,45,4,81,67,54,79,80,15,3,14,16,9,66,69,41,72,37,28,3,33,90,56,12,72,49,35,22,49,27,49,82,41,77,100,82,18,95,24,51,37,2,34,82,70,53,73,32,90,98,81,22,73,76,79,40,27,62,45,96,36,15,63,28,54,88,63,37,58,9,62,98,93,72,99,53,91,29,61,31,11,42,20,35,50,68,10,86 };
int arr[] = { 1, 5, 11, 5 };
vector<int> nums(arr, arr + 4);
bool flag = canPartition(nums);
nums.clear();
cout << flag <<endl;
}
其他
- 题目选自：分割等和子集
