分割等和子集
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
- 每个数组中的元素不会超过 100
- 数组的大小不会超过 200
示例 1:
代码语言：javascript复制输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].示例 2:
代码语言：javascript复制输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.一
代码语言：javascript复制// @lc code=start
class Solution {
private:
// 使用nums[0...index],是否可以完全填充一个容量为sum的背包
bool tryPartition(const vector<int> &nums, int index, int sum) {
if( sum == 0)
return true;
if( sum < 0 || index < 0)
return false;
return tryPartition(nums, index-1 ,sum) || tryPartition(nums, index-1, sum - nums[index]);
}
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for( int i = 0; i < nums.size(); i ) {
assert(nums[i] > 0);
sum = nums[i];
}
if ( sum %2 != 0)
return false;
return tryPartition(nums, nums.size()-1, sum/2);
}
};
// @lc code=end记忆化搜索
代码语言：javascript复制// @lc code=start
class Solution {
private:
// memo[i][c] 表示使用索引为[0...i]的这些元素，是否可以完全填充一个容量为c的背包
// -1 表示为未计算； 0 表示不可以填充；1 表示可以填充
vector<vector<int>> memo;
// 使用nums[0...index],是否可以完全填充一个容量为sum的背包
bool tryPartition(const vector<int> &nums, int index, int sum) {
if( sum == 0)
return true;
if( sum < 0 || index < 0)
return false;
if (memo[index][sum] != -1)
return memo[index][sum] == 1;
memo[index][sum] = (tryPartition(nums, index-1 ,sum) || tryPartition(nums, index-1, sum - nums[index])) ? 1 : 0;
return memo[index][sum] == 1;
}
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for( int i = 0; i < nums.size(); i ) {
assert(nums[i] > 0);
sum = nums[i];
}
if ( sum %2 != 0)
return false;
memo = vector<vector<int>>(nums.size(), vector<int>(sum/2 1, -1));
return tryPartition(nums, nums.size()-1, sum/2);
}
};
// @lc code=end动态规划
代码语言：javascript复制class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for (int i = 0; i < nums.size(); i) {
assert(nums[i] > 0);
sum = nums[i];
}
if( sum % 2)
return false;
int n = nums.size();
int C = sum / 2;
vector<bool> memo(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[j-nums[i]];
return memo[C];
}
};
