LeetCode 494 目标和
🟡中等
https://leetcode.cn/problems/target-sum/
显然可以用回溯求解
class Solution {
public:
vector<int> loc_nums;
vector<int> path;
int num =0;
void wri_at_index(int index,int max_index,int sum, int target){
if(index==max_index){
if(sum==target){
num+=1;
return;
}
return;
}
path.push_back(0+loc_nums[index]);
wri_at_index(index+1, max_index,sum+loc_nums[index],target);
path.pop_back();
path.push_back(0-loc_nums[index]);
wri_at_index(index+1, max_index, sum-loc_nums[index],target);
path.pop_back();
}
int findTargetSumWays(vector<int>& nums, int target) {
loc_nums = nums;
wri_at_index(0,nums.size(),0,target);
return num;
}
};
但是，设原数组和为sum，加上正负号后的和为target，那么有：正+正 = sum，正+负 = target，则正 = （sum+target）/2，那么转化为背包问题。
class Solution {
public:
int add_pack(vector<int>& nums,int index,int cap){
if(cap ==0) return 1;
if(index==nums.size()) {
return 0;
}
if(cap>=nums[index]){
return add_pack(nums,index+1,cap)+add_pack(nums,index+1,cap-nums[index]);
}else{
return add_pack(nums,index+1,cap);
}
}
int findTargetSumWays(vector<int>& nums, int target) {
int sum = accumulate(nums.begin(),nums.end(),0);
if((sum+target)%2){
return 0;
}
return add_pack(nums,0,(sum+target)/2);
}
};
这里出现了错误，cap等于0不能提前截断 ，这种针对本层输入的，一定要走到最后也就是index到最后才能返回，中途不能返回，
修改后
class Solution {
public:
int add_pack(vector<int>& nums,int index,int cap){
// if(cap ==0) return 1;
if(index==nums.size()) {
if(cap==0) return 1;
return 0;
}
if(cap>=nums[index]){
return add_pack(nums,index+1,cap)+add_pack(nums,index+1,cap-nums[index]);
}else{
return add_pack(nums,index+1,cap);
}
}
int findTargetSumWays(vector<int>& nums, int target) {
int sum = accumulate(nums.begin(),nums.end(),0);
if((sum+target)%2){
return 0;
}
return add_pack(nums,0,(sum+target)/2);
}
};
进一步修改为动态规划
class Solution {
public:
int add_pack(vector<int>& nums,int index,int cap){
// if(cap ==0) return 1;
if(index==nums.size()) {
if(cap==0) return 1;
return 0;
}
if(cap>=nums[index]){
return add_pack(nums,index+1,cap)+add_pack(nums,index+1,cap-nums[index]);
}else{
return add_pack(nums,index+1,cap);
}
}
int findTargetSumWays(vector<int>& nums, int target) {
int sum = accumulate(nums.begin(),nums.end(),0);
if((sum+target)%2||sum+target<0){
return 0;
}
int dp[(sum+target)/2+1];
memset(dp,0,sizeof dp);
dp[0] = 1;
for(int i = nums.size()-1;i>=0;i--){
for(int j =(sum+target)/2;j>=0;j--){
if(j>=nums[i]){
dp[j] = dp[j]+dp[j-nums[i]];
}else{
dp[j] = dp[j];
}
}
}
// return add_pack(nums,0,(sum+target)/2);
return dp[(sum+target)/2];
}
};