LeetCode 416 分割等和子集
🟡 中等
https://leetcode.cn/problems/partition-equal-subset-sum/description/
看到子集想到“灵神”说的“选不选的问题， 对于数组中的每个元素肯定是要选的，关键是分到哪个集合中：可以分到第一个，也可以分到第二个。
class Solution {
public:
bool add_path(vector<int>& nums,int index,int first,int second){
if(index==nums.size()){
if(first==second){
return true;
}
return false;
}
first+=nums[index];
if(add_path(nums,index+1,first,second)) return true;
first-=nums[index];
second+=nums[index];
if(add_path(nums,index+1,first,second)) return true;
second-=nums[index];
return false;
}
bool canPartition(vector<int>& nums) {
return add_path(nums,0,0,0);
}
};
或者 先求和，在累加看看能不能等于和的一半。
class Solution {
public:
bool add_path(vector<int>& nums,int index,int sum,int target){
if(sum>target) return false;
if(sum==target) return true;
if(index==nums.size()) return false;
if(add_path(nums,index+1,sum+nums[index],target)) return true;
if(add_path(nums,index+1,sum,target)) return true;
return false;
}
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(),nums.end(),0);
if(sum%2==1) return false;
return add_path(nums,0,0,sum/2);
}
};
如果要转化为dp数组，发现参数为三个数，那么应该是三维数组，但是这里看 add_path 的参数中的 sum 和 target 其实可以用他们之差 cap 作为参数，意思就是拿着cap容量的背包去装，装完也就是说cap==0了，那么就返回true 。
class Solution {
public:
bool add_path(vector<int>& nums,int index,int cap){
if(cap<0) return false;
if(cap==0) return true;
if(index==nums.size()) return false;
if(add_path(nums,index+1,cap-nums[index])) return true;
if(add_path(nums,index+1,cap)) return true;
return false;
}
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(),nums.end(),0);
if(sum%2==1) return false;
return add_path(nums,0,sum/2);
}
};
改为dp
- 因为本层需要 （index+1，cap）和（index+1，cap-nums[i]），因此数组行数：0-numsSize，列数：0-cap；
- 初始化：左边一列，cap等于0，因此为true；最底下一行index超了，因此为false。
- 遍历顺序：行从下到上，列从左到右。
class Solution {
public:
bool add_path(vector<int>& nums,int index,int cap){
if(cap<0) return false;
if(cap==0) return true;
if(index==nums.size()) return false;
if(add_path(nums,index+1,cap-nums[index])) return true;
if(add_path(nums,index+1,cap)) return true;
return false;
}
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(),nums.end(),0);
if(sum%2==1) return false;
bool dp[nums.size()+1][sum/2+1];
memset(dp,0,sizeof dp);
for(int i = 0;i<nums.size();i++){
dp[i][0] = true;
}
for(int i = 0;i<=sum/2;i++){
dp[nums.size()][i] =false;
}
for(int i = nums.size()-1;i>=0;i--){
for(int j = 1;j<=sum/2;j++){
if(dp[i+1][j]){
dp[i][j] =true;
continue;
}
if(j-nums[i]<0){
dp[i][j] = false;
continue;
}
if(dp[i+1][j-nums[i]]){
dp[i][j] = true;
}
}
}
return dp[0][sum/2];
}
};
这里还可以进一步优化，注意到本层只依赖于下一行，因此可以只维护一行就行。
这里注意，内层循环要倒过来了，如果从左到右：右边依靠左边的旧值就会被更新，进而导致答案错误。
class Solution {
public:
bool add_path(vector<int>& nums,int index,int cap){
if(cap<0) return false;
if(cap==0) return true;
if(index==nums.size()) return false;
if(add_path(nums,index+1,cap-nums[index])) return true;
if(add_path(nums,index+1,cap)) return true;
return false;
}
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(),nums.end(),0);
if(sum%2==1) return false;
bool dp[sum/2+1];
memset(dp,false,sizeof dp);
dp[0] = true;
for(int i = nums.size()-1;i>=0;i--){
for(int j = sum/2;j>=1;j--){
if(dp[j]){
dp[j] =true;
continue;
}
if(j-nums[i]<0){
dp[j] = false;
continue;
}
if(dp[j-nums[i]]){
dp[j] = true;
continue;
}
}
}
return dp[sum/2];
}
};