分割等和子集
給定一個隻包含正整數的非空數組。是否可以将這個數組分割成兩個子集，使得兩個子集的元素和相等。
注意:
- 每個數組中的元素不會超過 100
- 數組的大小不會超過 200
示例 1:
輸入: [1, 5, 11, 5]
輸出: true
解釋: 數組可以分割成 [1, 5, 5] 和 [11]. 複制
示例 2:
輸入: [1, 2, 3, 5]
輸出: false
解釋: 數組不能分割成兩個元素和相等的子集. 複制
一
// @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 複制
記憶化搜尋
// @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 複制
動态規劃
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];
}
}; 複制