##### 递归解法

``````class Solution {
private:
//目标和个数
int count;
//vector大小,减少递归函数里查询O(n)复杂度
int size;
public:
int findTargetSumWays(vector<int>& nums, int S) {
size = nums.size();
helper(nums,0,0,S);
return count;
}
private:
void helper(const vector<int>& nums,int len,int sum,int S){
if(len == size)
{
if(sum == S)
count++;
return;
}else{
helper(nums,len+1,sum+nums[len],S);
helper(nums,len+1,sum-nums[len],S);
}
}
};``````

``````Runtime: 1120 ms, faster than 19.53% of C++ online submissions for Target Sum.
Memory Usage: 8.9 MB, less than 98.13% of C++ online submissions for Target Sum.``````

#### 递归加记忆化

``````class Solution {
private:
int target;
int vec_size;
public:
int findTargetSumWays(vector<int>& nums, int S) {
target = S;
vec_size = nums.size();
vector<unordered_map<int,int>> mem(nums.size());
return helper(nums,0,0,mem);
}
private:
int helper(const vector<int> & nums,int loc,int sum,vector<unordered_map<int,int>> &mem) {
if(loc == vec_size)
return sum == target;
auto iter = mem[loc].find(sum);
if(iter != mem[loc].end()) return iter->second;
mem[loc][sum] = helper(nums,loc+1,sum+nums[loc],mem) + helper(nums,loc+1,sum-nums[loc],mem);
return mem[loc][sum];
}
};``````

``````Runtime: 216 ms, faster than 36.79% of C++ online submissions for Target Sum.
Memory Usage: 61.2 MB, less than 9.71% of C++ online submissions for Target Sum.``````

#### 动态规划解法

``````class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
unordered_map<int,int> cur{{0,1}},next;
for(int i = 0;i < nums.size();i++)
{
for(auto& it : cur)
{
next[it.first + nums[i]] += it.second;
next[it.first - nums[i]] += it.second;
}
swap(cur,next);
next.clear();
}

return cur[S];
}
};``````

``````Runtime: 140 ms, faster than 45.56% of C++ online submissions for Target Sum.
Memory Usage: 35.4 MB, less than 30.00% of C++ online submissions for Target Sum.``````

``````cur = 0 next 1 -1
---------
cur = -1 next 0 -2
cur = 1 next 2 0
---------
cur = 2 next 3 1
cur = 0 next 1 -1
cur = -2 next -1 -3
---------
cur = -3 next -2 -4
cur = -1 next 0 -2
cur = 1 next 2 0
cur = 3 next 4 2
---------
cur = 0 next 1 -1
cur = 2 next 3 1
cur = -4 next -3 -5
cur = 4 next 5 3
cur = -2 next -1 -3
---------``````