题目

简单的dfs爆搜回溯

擦墙而过

class Solution {
public:
int n;int findTargetSumWays(vector<int>& nums, int target) {n = target;backtrack(nums,0,0);return res;}
private:
int res = 0;void backtrack(vector<int>&nums,int pos,int target){if(pos==nums.size()){if(target==n)res++;return;}backtrack(nums,pos+1,target+nums[pos]);backtrack(nums,pos+1,target-nums[pos]);}
};

记忆化优化

主要慢在C++的字符串转化上面，用java或者python会快很多。实际上C++直接用数组牺牲1000个空间用1000+target来作为键至少内存占用会少很多

class Solution {
public:
int n;int findTargetSumWays(vector<int>& nums, int target) {n = target;return backtrack(nums,0,0);}
private:
//用string制作备忘录，由于数组无法基于负数做备忘
unordered_map<string,int>memo;int backtrack(vector<int>&nums,int pos,int target){string s = to_string(pos)+','+to_string(target);if(memo.count(s)){return memo[s];}if(pos==nums.size()){if(target==n)return 1;return 0;}return  memo[s] = backtrack(nums,pos+1,target+nums[pos])+backtrack(nums,pos+1,target-nums[pos]);}
};

(重头戏)子集背包dp

题目详解

• 将整个加减过程分为两个子集，一个专门的'-'号，一个专门的'+'号，即A-B = target=>A+A = target+A+B

• 得到A = (target + sum(A+B))/2.把A看成子集背包中背包需要装下的值，我们现在只需要判断nums中存在多少个使得背包正好填满的情况。既然是背包问题，则牵扯到装与不装,dp[i][j] = dp[i-1][j](no pack)+dp[i-1][j-nums[i]](pack);

• base case:dp[0][..] = 0,dp[...][0] = 1(注意这个是不取任何数的基本情况，后面还是需要更新这个值(毕竟可能存在和为0，故第二层循环需要从0开始遍历而不是1))

• 根据base case和状态转移方程可以确定遍历方向可以是从左往右or从右往左(为滚动数组埋下伏笔)，从上往下。

代码详解

• 当然对于子集背包求和问题还有两个重要细节(因题而异)

1. 确认正负关系
2. 确认奇偶性

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;for(int a:nums)sum += a;int pack = (target+sum)/2;int n = nums.size();//判断特殊条件(这两种特殊情况不可能存在非负数子集和)if(target>sum||(target+sum) %2 ==1)return 0;vector<vector<int>>dp(n+1,vector<int>(pack+1));for(int i=0;i<=n;i++)dp[i][0] = 1;for(int i=1;i<=n;i++){for(int j=0;j<=pack;j++){dp[i][j] = dp[i-1][j];if(j>=nums[i-1])dp[i][j] += dp[i-1][j-nums[i-1]];}}return dp[n][pack];}};

滚动数组优化

• 由于dp关系只和上一行的值有关(可以滚动一维)，而又为了保证[j-nums[i-1]]取的是上一行的数据，需要从右往左遍历(反正从右往左也包含了base case符合条件)

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;for(int a:nums)sum += a;int pack = (target+sum)/2;int n = nums.size();//判断特殊条件(这两种特殊情况不可能存在非负数子集和)if(target>sum||(target+sum) %2 ==1)return 0;vector<int>dp(pack+1);dp[0] = 1;for(int i=1;i<=n;i++){//从右往左遍历for(int j=pack;j>=0;j--){dp[j] = dp[j];if(j>=nums[i-1])dp[j] += dp[j-nums[i-1]];}}return dp[pack];}};