分割等和子集
给定一个非空的正整数数组 nums ，请判断能否将这些数字分成元素和相等的两部分。
Link
错误思路
TLS的思路：
记录下所有子集在mp中，但是会造成超时
class Solution {
public:
bool canPartition(vector<int>& nums) {
//分成元素和相同的两个部分
int sum=0;
int n=nums.size();
unordered_map<int,bool>mp;
mp[nums[0]]=true;
sum=nums[0];
//dp[nums[i]]=dp[sum-nums[i]]
for(int i=1;i<n;i++){
sum+=nums[i];
unordered_map<int,bool>temp_mp;
temp_mp=mp;
for(auto m :temp_mp){
mp[m.first+nums[i]]=true;
}
}
if(sum%2){
return false;
}else{
if(mp.find(sum/2)!=mp.end()){
return true;
}else{
return false;
}
}
}
};
同理，DFS也会超时
class Solution {
public:
int sum;
int n;
vector<int>arr;
bool dfs(int index,int temp_sum){
temp_sum+=arr[index];
if(temp_sum>sum){
return false;
}else if(temp_sum==sum){
return true;
}else{
for(int i=index+1;i<n;i++){
if(dfs(i,temp_sum)){
return true;
}
}
return false;
}
}
bool canPartition(vector<int>& nums) {
//分成元素和相同的两个部分
sum=0;
n=nums.size();
arr=nums;
for(int i=0;i<n;i++){
sum+=nums[i];
}
if(sum%2){
return false;
}else{
sum=(sum>>1);
}
for(int i=0;i<n;i++){
if(dfs(i,0)){
return true;
}
}
return false;
}
};
正确思路
其实可以理解成为一个NP问题，用0-1背包的思想来解决
dp[i][j]表示遍历到第i个元素的时候，总和为j的可能是“真/假”,则关系为：
- 当j>=nums[i]的时候，dp[i][j]=dp[i-1][j-nums[i]]|dp[i-1][j];
- 当j<=nums[i],只有一种可能，就是不算上当前货物，dp[i][j]=dp[i-1][j];
需要注意，因为数组一开始预设为dp[index下标个数][和的一半],所以要考虑边界条件，也就是如果数组中由一个数字大于和的一半,必然返回false,比如例子[99,1]
class Solution {
public:
bool canPartition(vector<int>& nums) {
int n=nums.size();
if(n<2){
return false;
}
int sum=0;
int max_value=0;
for(int i=0;i<n;i++){
sum+=nums[i];
if(nums[i]>max_value){
max_value=nums[i];
}
}
if(sum%2){
return false;
}
sum=(sum>>1);
if(max_value>sum){
return false;
}
vector<vector<bool> >dp(n+1,vector<bool>(sum+1,0));
for(int i=0;i<n;i++){
dp[i][0]=true;
}
dp[0][nums[0]]=true;
for(int i=1;i<n;i++){
for(int j=1;j<=sum;j++){
if(j>=nums[i]){
dp[i][j]=dp[i-1][j-nums[i]]|dp[i-1][j];
}else{
dp[i][j]=dp[i-1][j];
}
}
}
return dp[n-1][sum];
}
};